[백준] 1520번 : 내리막 길 (파이썬)

DFS + Memorization 문제 (DFS로만 풀 시 시간초과)

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

1520번: 내리막 길

 

(1) 시간초과난 코드 (실패)

# 내리막 길 (골드 3) / DFS-recursion (시간 초과)
import sys
r, c = map(int, sys.stdin.readline().split())
arr = []
visit = [[False] * c for _ in range(r)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
cnt = 0
for _ in range(r):
    col = list(map(int, sys.stdin.readline().split()))
    arr.append(col)

def dfs(x, y):
    global cnt, value
    # visit[x][y] = True
    if x == c - 1 and y == r - 1 : cnt += 1
    value = arr[y][x]
    
    for i in range(4):
        nextX = x + dx[i]
        nextY = y + dy[i]
        
        if nextX >= 0 and nextX < c and nextY >= 0 and nextY < r:
            if arr[nextY][nextX] < arr[y][x]: # (1) !!!
                dfs(nextX, nextY)
dfs(0,0)      
print(cnt)

 

1) dfs-recursion 짜는데에서 문제

다음 좌표값 arr[nextY][nextX]와 현재 좌표값 arr[y][x]를 비교해서 다음 좌표값이 더 작으면 dfs를 재귀호출하는 방식이다. 나는 저 arr[y][x]를 뭔가 많이 사용할 것 같아서 value라는 변수로 따로 빼두었었다. 그리고 저 주석 부분에서 arr[y][x]와 비교하는게 아니라 저장해둔 value와 비교했었다. 

 

그러니까 cnt 출력으로 3을 출력해야 하는데 계속 1이 나왔다. 그 이유는 dfs에서 리턴한 후 다시 for문 처음을 돌아가서 if문에 걸려

if arr[nextY][nextX] < arr[y][x]:를 비교하게 되는데 마지막으로 dfs 재귀호출하여 함수 도입부에서 바꿔준 value값 10(마지막 좌표의 value값)이 계속 남아있게 돼서 이 값이랑만 계속 비교하게 된다. 따라서, 10보다 더 작은 값이 위에는 없으므로 경로 1개만 찾게 되는 것이다.

나는 이거 때문에 이 문제를 dfs-stack 방식으로도 풀어보았었는데 그때는 3이 잘 출력되었다. stack 방식에서는 value값 업데이트 위치를 while문 안에 적절히 잘 넣어줬기 때문에 당연히 잘 출력될 수 밖에 없었다..

 

또, visit 배열은 일단 만들어놨는데 사용하진 않았다. 이미 방문한 곳일지라도 0,0부터 마지막 좌표까지 갈 수 있는 모든 경로를 다 탐색해야 하므로 재방문할 수도 있기 때문이다. 이것때문에 혹시나 불안했는데 역시 16퍼에서 시간초과남 .. 애초에 이문제는 DFS로만 풀시 시간초과가 날수밖에 없는 문제였다.

 

2) dfs-recursion + memorization 방식 도입

알고리즘 수업시간에 배운 memorization 방식이 생각났다. 다른 블로그를 참고하니 이문제는 dfs + dp라고 소개해둔데가 많은데 엄밀하게 말하면 dfs + memorizaion 방식이 맞는 것 같다. (이거 때문에 골드 3인듯 함.)

 

(2) 수정한 코드 (성공)

# 내리막 길 (골드 3) / DFS-recursion + memorization (성공)
import sys
r, c = map(int, sys.stdin.readline().split())
arr = []
memo = [[-1] * c for _ in range(r)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
for _ in range(r):
    col = list(map(int, sys.stdin.readline().split()))
    arr.append(col)

def dfs(x, y):
    if x == c - 1 and y == r - 1 : return 1

    if memo[y][x] != -1 : return memo[y][x] # 기존에 기록해둔 memo 값이 있을시 사용, 재귀호출 X (memorization 핵심!)

    route = 0
    for i in range(4):
        nextX = x + dx[i]
        nextY = y + dy[i]
        
        if nextX >= 0 and nextX < c and nextY >= 0 and nextY < r:
            if arr[nextY][nextX] < arr[y][x]:
                route += dfs(nextX, nextY)
    memo[y][x] = route
    return memo[y][x]

print(dfs(0,0))

 

memorization 기법을 사용하였다. 

기존의 cnt 변수를 지우고, dfs에 리턴값을 주는 방식으로 변경하였다. 마지막 좌표값일시 1을 리턴한다. for문 안에서 dfs 재귀호출한게 리턴할시 route라는 변수에 경로의 가짓수를 더해주고, for문을 빠져나오면 해당 x,y좌표의 memo 배열 값을 route로 업데이트해준다.