백준 1520) 내리막길_Python

문제 분석

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

• 처음에는 단순하게 프로그래머스의 등굣길 문제 느낌으로 풀려고 했다. BFS+DP 방식이다. 

for r in range(0,M):
    for c in range(0,N):
        for i in range(4):
            nr,nc=r+dr[i],c+dc[i]
            if DP[r][c]!=0 and 0<=nr<M and 0<=nc<N:
                if height[r][c]>height[nr][nc]:
                    if DP[nr][nc]==0: 
                    #다음 노드가 탐색된 적이 없으면 다음 노드를 지나는 경로는 오직 이번 노드를 지나는 경로의 개수라는 뜻 
                        DP[nr][nc]=DP[r][c]
                    else:
                    #다음 노드가 탐색된 적이 있다면, 이미 갱신된 경로 개수 값+이번 노드를 지나는 경로 개수 값
                        DP[nr][nc]=DP[nr][nc]+DP[r][c]

• 그러나 해당 내리막길 문제는 저런 방식으로 풀면 의도와는 다르게 누락되는 부분이 생긴다. 아래 그림에서 보았듯이 20->25로 가는 길에 20의 경로 개수가 2로 갱신이 되는데, 이미 20의 아래부분인 17은 1로 갱신된 후이다. 17을 탐색할 때는 20으로 갈 수가 없으니 20은 탐색이 안되고, 17은 그대로 1로 유지가 된다. 따라서 이 방법은 옳지 않다는 생각이 들었다. 그래서 방법을 DFS로 전환했는데  조금 서치를 해보니 BFS로도 풀수 있는 듯 하다? 🤔 이 방법은 추후에 좀 더 생각해 보려고 한다.

 

• DP,DFS(백트래킹)을 통해서 풀면 시간 초과도 없이 빠르게 문제를 풀 수 있는 것 같다.
• 우선 (0,0)에서 탐색을 시작한 후, 다음 노드로 이동할 수 있다면 DFS를 계속 이어간다. 탐색되는 순서는 임의로 우->하->좌->상으로 생각한다.
• DFS가 Return되는 지점은 두 지점이 생긴다.
  • 끝 지점에 도달하면 경로 1개가 추가된 것이므로, 1을 리턴해준다.
  • 만약 해당 노드가 이미 탐색된 부분이라면 visited[r][c]값, 즉 해당 노드를 지나는 경로 값을 리턴해준다.
    • 이게 직관적이지 않을 수는 있지만, 위의 두 그림을 보자. 저 두 경로는 20이 탐색되는 순간부터 경로가 겹치기 시작한다. 따라서 2번째 그림 에서 25->20으로 가는 순간 해당 경로는 더 이상 탐색할 필요가 없다. 이미 10~20까지 경로가 1개 존재한다는 의미이므로, 여기서 20 노드의 값을 리턴해주면 된다.
    • 이제 다시 32로 dfs가 return되면 30을 거치는 경로 1개+20을 거치는 경로 1개가 더해져 32의 노드 값은 2개가 된다.
    • 이제 첫 번째 경로를 보면 어디서 return이 되는지 보일 것이다. 15에서부터 경로가 겹치기 시작하므로 1이 리턴될 것이고, 35~15까지의 값은 경로가 1개로 된다. 마지막으로 리턴되는 최초 값인 50노드는 경로 1개+경로 2개가 더해져 3이 리턴되면서 최종적으로 dfs가 종료된다. 

 

 

코드

import sys
input=sys.stdin.readline
M,N=map(int,input().split())
sys.setrecursionlimit(10**7) #재귀제한 안풀어주면 오류가 발생한다.

height=[list(map(int,input().split())) for _ in range(M)]
visited=[[-1]*(N) for _ in range(M)]


dr=[0,1,0,-1]
dc=[1,0,-1,0]

def dfs(r,c):

    if r==M-1 and c==N-1:
        visited[r][c]=1
        return 1

    if visited[r][c]!=-1:
        #이미 해당 경로가 탐색 된것이므로 더 이상 탐색할 필요가 없다.
        #visited[r][c]=0이라면 해당 경로로 갈 수 없는 것이므로 그대로 0을 리턴받으면 되고, 
        #경로가 있다면 그 값을 리턴받는 것
        return visited[r][c]
    
    #해당 노드는 탐색 처리를 해준다.
    visited[r][c]=0

    for i in range(4):
    	#다음으로 탐색할 노드 결정
        nr,nc=r+dr[i],c+dc[i]

        if 0<=nr<M and 0<=nc<N: 
            if height[r][c]>height[nr][nc]:
                visited[r][c]+=dfs(nr,nc)

    return visited[r][c]
    

print(dfs(0,0))

visited 배열 값은 아래와 같이 확인할 수 있다.