[백준] 내리막 길 (1520번) - Python/알고리즘

✅문제 - 내리막 길 (1520번)

---

 

✅필요 알고리즘 개념 - DP/DFS

---

🔵 DFS 와 BFS 중 무엇을 쓸 것인가

◼ 이 문제는 경로 찾기 문제와 유사하므로 DFS와 BFS 중 하나를 써야 하는데 왜 DFS를 사용할까?

이 문제의 경우 경로가 겹칠 때 다른 경로에게 영향을 주기 때문에 먼저 DFS로 한 경로를 끝까지 탐색하는 것이 유리하다.

 

🔵 DP 사용 법 

◼ 2차원 리스트에 (x,y)에서 (row,col) 까지 가는 경우의 수를 저장한다. DFS를 진행하던 도중 이미 들렀던 지점인 경우에는 바로 dp 값을 사용한다.

 

✅코드 설명

---

import sys

row,col = map(int,sys.stdin.readline().rstrip().split())
board = [] 
delta = [(1,0),(-1,0),(0,1),(0,-1)]

dp = [ [-1 for _ in range(col)] for _ in range(row)]
# dp의 초깃값을 -1로 설정한다. 들리지 않은 경우를 -1로 하기 위함
# -1로 설정하는 것이 굉장히 중요하다!
# 왜냐하면 0으로 설정하면 들렸는데 경로의 수가 0인 건지
# 아니면 안들린건지 판별이 불가능하기 때문에
# 들렸는데 경로의 수가 0인 경우에도 계속 방문을 하게 됨
# 하지만 -1로 초기화 후에 들렸는데 경로가 0인 경우에는
# dp 값이 0 이기 때문에 들렸다는 것을 확인이 가능하다

for _ in range(row):
    board.append(list(map(int,sys.stdin.readline().rstrip().split())))

def dfs(y,x):
    if y == row -1  and x == col - 1:
        return 1
        # 도착 지점에 도달한 경우 경로의 수를 1 추가
        # 재귀를 돌아가며 (row,col) 부터 (0,0) 까지 돌아가면서
        # 들렸던 모든 지점의 dp[y][x]에 +1 을 함
    
    # 이미 들렀던 경우에는
    # (y,x) 에서(row,col) 까지 가는 경로의 수인
    # dp[y][x]를 호출 하고 DFS 종료
    if dp[y][x] != -1:
        return dp[y][x]
    
    dp[y][x] = 0
    # 0으로 바꿔서 들렸다고 표시하고 row,col 까지 가는 경로의 수를 0으로 초기화
    
    for dy,dx in delta:
        ny,nx = y+dy,x+dx

        if  ny == -1 or ny == row or nx == -1 or nx == col :
            continue
        if board[y][x] <= board[ny][nx]:
            continue
        dp[y][x] += dfs(ny,nx)

    return dp[y][x]

print(dfs(0,0))