[ 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)

좋은 웹페이지 즐겨찾기