[백준] 1520 내리막길 [Python]

이 문제는 얼핏하면 dfs, bfs처럼 보여서 나도 처음에는 dfs로만 구현을 했었다.

하지만 dfs로 구현하면 값이 커질수록 반복되는 구간이 증가하기때문에 당연히 시간초과가 났었고 이를 고치기 위해 dp를 이용한 방법을

추가시켰다.

처음에는 dp를 어떻게 적용해야하는지가 감이 안와서 주변 친구들에게 도움을 받아서 이해를 하게 되었다.

 

이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다. 이 관점으로 코드를 구현해보자.

 

 

우선 처음에 dfs만 구현해서 시간초과가 난 코드이다.

from sys import stdin as s
import sys
sys.setrecursionlimit(10**5)
s= open('input.txt','rt')

def dfs(x,y):
    global cnt
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx<n and 0<=ny<m: 
                if arr[x][y] > arr[nx][ny]:
                    if dp[nx][ny] !=0:
                        dp[nx][ny] = dp[nx][ny]+1
                    else:
                        dp[nx][ny] += dp[x][y]
                        
                    dfs(nx,ny)
    
if __name__=='__main__':
    n,m = map(int,s.readline().split())

    arr = [list(map(int,s.readline().split()))for _ in range(n)]
    dp=[[0]*m for _ in range(n)]
    dp[0][0]=1
    cnt=0
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    dfs(0,0)
    
    print(dp[n-1][m-1])

 

 

---

 

m,n = map(int,s.readline().split())

    arr = [list(map(int,s.readline().split()))for _ in range(m)]
    
    #dp를 0이 아닌 -1로 초기화하는 이유는 방문여부를 알기 위해 -1로 초기화합니다.
    dp=[[-1]*n for _ in range(m)]
    
    #우,하,좌,상 순서
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

 

위의 방식과 다른점은 dp를 -1로 초기화 시켜준다는 점이다. 

dp를 0이 아닌 -1로 초기화 시켜주는 이유는 방문여부(visted)를 알기 위하여 -1로 초기화 한다.

 

# dfs 함수 정의
def dfs(x,y):
    
    #x,y 값이 오른쪽끝에 도달하면 1 return
    if x == m-1 and y == n-1:
        return 1
    
    #dp[x][y]가 -1이 아닌 뜻은 이미 갔던 경로이기때문에 
    #다시 방문하지않고 바로 현재dp[x][y]값을 return해준다.
    if dp[x][y] != -1:
        return dp[x][y]      

    #경로의 수를 저장하는 ways변수 선언
    ways=0
    
    for i in range(4):
        # 4가지 방향 탐색 (우,하,좌,상) 순서
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<m and 0<=ny<n and arr[x][y] > arr[nx][ny]:
            #ways 에 dfs값을 더해주면서 이동.
            ways += dfs(nx,ny)
    
    #목표지점갈때까지 ways는 -1로 찍히고 돌아오면서 ways값에 1리턴해준것을 찍으면서 온다.
    dp[x][y] = ways
    return dp[x][y]

 

 

위의 코드는 dfs 함수 부분인데 실행해보면 아래와 같이 dp값들이 변하면서 dfs(0,0)의 값이 출력된다.

아래 과정은 우선 오른쪽 마지막까지 갔다가 돌아오면서 return으로 받은 1을 찍으면서 오다가 경로가 추가되면 1씩 증가하면서 오는 과정이다.  그래서 아래 배열을 보면 처음시작부분에서 3가지의 경로로 갈 수 있다는 뜻이 된다. 

 

 

디버깅 사진

 

전체코드

from sys import stdin as s
import sys
sys.setrecursionlimit(10**8)
s= open('input.txt','rt')

# dfs 함수 정의
def dfs(x,y):
    
    #x,y 값이 오른쪽끝에 도달하면 1 return
    if x == m-1 and y == n-1:
        return 1
    
    #dp[x][y]가 -1이 아닌 뜻은 이미 갔던 경로이기때문에 
    #다시 방문하지않고 바로 현재dp[x][y]값을 return해준다.
    if dp[x][y] != -1:
        return dp[x][y]      

    #경로의 수를 저장하는 ways변수 선언
    ways=0
    
    for i in range(4):
        # 4가지 방향 탐색 (우,하,좌,상) 순서
        nx = x + dx[i]
        ny = y + dy[i]

        if 0<=nx<m and 0<=ny<n and arr[x][y] > arr[nx][ny]:
            #ways 에 dfs값을 더해주면서 이동.
            ways += dfs(nx,ny)
    
    #목표지점갈때까지 ways는 -1로 찍히고 돌아오면서 ways값에 1리턴해준것을 찍으면서 온다.
    dp[x][y] = ways
    return dp[x][y]

if __name__=='__main__':
    m,n = map(int,s.readline().split())

    arr = [list(map(int,s.readline().split()))for _ in range(m)]
    
    #dp를 0이 아닌 -1로 초기화하는 이유는 방문여부를 알기 위해 -1로 초기화합니다.
    dp=[[-1]*n for _ in range(m)]
    
    #우,하,좌,상 순서
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]

    print(dfs(0,0))