[ BOJ / Python ] 14890번 경사로
이번 문제는 삼성 기출 문제로, 조건들을 따져가며 구현하는 방식으로 해결하였다. 컬럼을 확인하는 함수 chk_column과 로우를 확인하는 함수 chk_row를 작성하였다.
- 아래에서 위로 향하며 연속되는 수의 갯수를 DP를 이용하여 dp1에 저장한다.
- 위에서 아래로 향하며 연속되는 수의 갯수를 DP를 이용하여 dp2에 저장한다.
- 아래에서 위로 향하며 인접한 값과 비교하며 1 차이가 날 경우에 dp1을 이용하여 l과 비교하고, 해당 자리에 경사로가 건설되지 않았다면 경사로를 만들어준다.
- 위에서 아래로 향하며 인접한 값과 비교하며 1 차이가 날 경우에 dp2를 이용하여 l과 비교하고, 해당 자리에 경사로가 건설되지 않았다면 경사로를 만들어준다.
이 방식을 column, row에 대해 따로 따로 구현하였고, 해결할 수 있었다. 문제를 푸는 과정에서 방향이 많이 헷갈려서 오래 걸렸던 문제였다.
Code
n, l=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
answer=0
def chk_column():
global answer
g=[[0 for _ in range(n)] for _ in range(n)]
dp1=[[1 for _ in range(n)] for _ in range(n)]
dp2=[[1 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n-2, -1, -1):
if grid[j][i]==grid[j+1][i]:
dp1[j][i]=dp1[j+1][i]+1
for j in range(1, n):
if grid[j][i]==grid[j-1][i]:
dp2[j][i]=dp2[j-1][i]+1
for i in range(n):
chk=True
for j in range(n-2, -1, -1):
if grid[j+1][i]+1==grid[j][i]:
if dp1[j+1][i]<l:
chk=False
break
elif dp1[j+1][i]>=l:
c=True
for k in range(l):
if g[j+1+k][i]>=1:
c=False
break
if c:
for k in range(l):
g[j+1+k][i]+=1
else:
chk=False
break
if abs(grid[j+1][i]-grid[j][i])>1:
chk=False
break
if not chk:
continue
for j in range(1, n):
if grid[j-1][i]+1==grid[j][i]:
if dp2[j-1][i]<l:
chk=False
break
elif dp2[j-1][i]>=l:
c=True
for k in range(l):
if g[j-1-k][i]>=1:
c=False
break
if c:
for k in range(l):
g[j-1-k][i]+=1
else:
chk=False
break
if chk:
answer+=1
def chk_row():
global answer
g=[[0 for _ in range(n)] for _ in range(n)]
dp1=[[1 for _ in range(n)] for _ in range(n)]
dp2=[[1 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n-2, -1, -1):
if grid[i][j]==grid[i][j+1]:
dp1[i][j]=dp1[i][j+1]+1
for j in range(1, n):
if grid[i][j]==grid[i][j-1]:
dp2[i][j]=dp2[i][j-1]+1
for i in range(n):
chk=True
for j in range(n-2, -1, -1):
if grid[i][j+1]+1==grid[i][j]:
if dp1[i][j+1]<l:
chk=False
break
elif dp1[i][j+1]>=l:
c=True
for k in range(l):
if g[i][j+1+k]>=1:
c=False
break
if c:
for k in range(l):
g[i][j+1+k]+=1
else:
chk=False
break
if abs(grid[i][j+1]-grid[i][j])>1:
chk=False
break
if not chk:
continue
for j in range(1, n):
if grid[i][j-1]+1==grid[i][j]:
if dp2[i][j-1]<l:
chk=False
break
elif dp2[i][j-1]>=l:
c=True
for k in range(l):
if g[i][j-1-k]>=1:
c=False
break
if c:
for k in range(l):
g[i][j-1-k]+=1
else:
chk=False
break
if chk:
answer+=1
chk_column()
chk_row()
print(answer)
n, l=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(n)]
answer=0
def chk_column():
global answer
g=[[0 for _ in range(n)] for _ in range(n)]
dp1=[[1 for _ in range(n)] for _ in range(n)]
dp2=[[1 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n-2, -1, -1):
if grid[j][i]==grid[j+1][i]:
dp1[j][i]=dp1[j+1][i]+1
for j in range(1, n):
if grid[j][i]==grid[j-1][i]:
dp2[j][i]=dp2[j-1][i]+1
for i in range(n):
chk=True
for j in range(n-2, -1, -1):
if grid[j+1][i]+1==grid[j][i]:
if dp1[j+1][i]<l:
chk=False
break
elif dp1[j+1][i]>=l:
c=True
for k in range(l):
if g[j+1+k][i]>=1:
c=False
break
if c:
for k in range(l):
g[j+1+k][i]+=1
else:
chk=False
break
if abs(grid[j+1][i]-grid[j][i])>1:
chk=False
break
if not chk:
continue
for j in range(1, n):
if grid[j-1][i]+1==grid[j][i]:
if dp2[j-1][i]<l:
chk=False
break
elif dp2[j-1][i]>=l:
c=True
for k in range(l):
if g[j-1-k][i]>=1:
c=False
break
if c:
for k in range(l):
g[j-1-k][i]+=1
else:
chk=False
break
if chk:
answer+=1
def chk_row():
global answer
g=[[0 for _ in range(n)] for _ in range(n)]
dp1=[[1 for _ in range(n)] for _ in range(n)]
dp2=[[1 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n-2, -1, -1):
if grid[i][j]==grid[i][j+1]:
dp1[i][j]=dp1[i][j+1]+1
for j in range(1, n):
if grid[i][j]==grid[i][j-1]:
dp2[i][j]=dp2[i][j-1]+1
for i in range(n):
chk=True
for j in range(n-2, -1, -1):
if grid[i][j+1]+1==grid[i][j]:
if dp1[i][j+1]<l:
chk=False
break
elif dp1[i][j+1]>=l:
c=True
for k in range(l):
if g[i][j+1+k]>=1:
c=False
break
if c:
for k in range(l):
g[i][j+1+k]+=1
else:
chk=False
break
if abs(grid[i][j+1]-grid[i][j])>1:
chk=False
break
if not chk:
continue
for j in range(1, n):
if grid[i][j-1]+1==grid[i][j]:
if dp2[i][j-1]<l:
chk=False
break
elif dp2[i][j-1]>=l:
c=True
for k in range(l):
if g[i][j-1-k]>=1:
c=False
break
if c:
for k in range(l):
g[i][j-1-k]+=1
else:
chk=False
break
if chk:
answer+=1
chk_column()
chk_row()
print(answer)
Author And Source
이 문제에 관하여([ BOJ / Python ] 14890번 경사로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-14890번-경사로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)