백준1520_내리막 길

• https://www.acmicpc.net/status?user_id=gusehd502&problem_id=1520&from_mine=1
  

N, M = map(int,input().split())
G = [[0] * (M + 2)] + [[0] + list(map(int,input().split())) + [0] for _ in range(N)] +[[0] * (M + 2)]
dp = [[-1] * (M + 2) for _ in range(N + 2)]
dp[1][1] = 1

def DFS(r,c):
    if dp[r][c] == -1:
        dp[r][c] = 0
        for dr, dc in ((1,0),(0,1),(-1,0),(0,-1)):
            nr, nc = r + dr, c + dc
            if G[nr][nc] > G[r][c]:
                dp[r][c] += DFS(nr,nc)

    return dp[r][c]

print(DFS(N,M))

• DFS를 재귀 형태 풀어낸 DP문제이다.
• 도착 지점에서 DFS를 시작하여 한번 탐색한 지점에 도달했을 때 그 지점의 DP테이블에 기록 되어있는 경로 수를 반환한다.

(1) 첫 번째 케이스 살펴보기

• 맨 처음 그래프가 초기 상태이다.
• DFS 함수 내에서 for문으로 들어와 nr,nc 다음경로를 가지고 재귀한다.
• 이렇게 멈추게 되는 지점까지 dp테이블을 0이 값을 넣으며 전진한다.
• dp[0][0] == 1 인 값에 도달하면 1을 반환하여 지금까지 거쳐온 DP테이블 지점에 값을 누적하여 되돌아간다.
• 이 과정을 반복한다.

💯 DFS를 재귀로 코드를 짜보는 연습이 필요할 듯하다.