2차원 배열에서 경로의 개수 구하기 - 최단 경로가 아닌 경우

1. 문제

 

1520번: 내리막 길 (acmicpc.net)

1520번: 내리막 길

 

 

2. 풀이

 

이 문제에서 핵심은 "어떤 칸을 최초 방문할 때 해당 칸에서 목적지까지 도달할 수 있는 경우의 수에 대한 정보를 기록해 놓고, 다음 방문 시 기록된 값을 참조해서 반복된 연산을 피하는 것이다"

 

dp[y][x]를 (x,y)에서 (n-1,m-1)까지 조건에 맞는, 도달하는 경우의 수라고 정의하자.

 

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

maps = [list(map(int,stdin.readline().split())) for _ in range(m)]

dp = [[0]*n for _ in range(m)]

 

출발점은 (0,0)이고 도착점은 (n-1,m-1)이다.

 

DFS를 활용해 목적지까지 도달하는 경우 경우의 수에 1을 더해준다.

 

from sys import stdin

def dfs(x,y,n,m,maps):
    
    if x == n-1 and y == m-1:

        return 1
    
    else:
        
        if dp[y][x] == 0:

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= m-1:
                    
                    if maps[y][x] > maps[dy][dx]:
                        
                        dp[y][x] += dfs(dx,dy,n,m,maps)
        
        return dp[y][x]

 

x,y에서 경우의 수가 0이라면... 4방향 탐색을 시도한다..

 

다음 지점 dx,dy가 현재 지점 x,y보다 높이가 작다면 dx,dy로 dfs 탐색을 수행한다

 

그리고 그 결과를 현재 x,y지점에서 n-1,m-1로 가는 경우의 수 dp[y][x]에 더해준다.

 

------------------------------------------------------------------------------------------------------------------

 

여기서 DFS의 핵심은..

 

어떤 위치 x,y에서 for문을 모두 돌았다면...

 

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= m-1:
                    
                    if maps[y][x] > maps[dy][dx]:
                        
                        dp[y][x] += dfs(dx,dy,n,m,maps)

 

x,y에서 n-1,m-1까지 가는 경로를 모두 탐색해봤다는 뜻이다.

 

이 for문을 탈출하면 x,y에서 n-1,m-1까지 가는 경우의 수는 dp[y][x]에 결정이 된다.

 

------------------------------------------------------------------------------------------------------------------

 

따라서 탐색을 계속 하다가.. 어느 순간 dp[y][x]가 0이 아니라면..

 

이미 그 지점에서 n-1,m-1까지 가는 경우의 수는 dp[y][x]로 계산이 끝났으니까 바로 dp[y][x]를 return하면 된다

 

근데 이렇게 하면 시간초과가 나는데..

 

이제 왜 그런지 생각해보면

 

어떤 지점 x,y에서 탐색을 끝냈더니 목적지까지 도달하지 못해서 경우의 수가 0이라 dp[y][x] = 0이 되었는데..

 

그 후 다시 다른 경로를 탐색하다가 x,y지점으로 들어왔을때, dp[y][x] = 0이므로, 얘는 이전에 이미 탐색을 끝내서 0인데도..

 

현재 코드는 dp[y][x] = 0이면 dfs로 탐색하라고 하니까 이미 탐색 해본 곳을 또 탐색해보는 반복적인 연산을 수행하게 된다

 

그래서 시간 초과가 뜨는데..

 

결국에 dp 초기화 할때 목적지까지 도달하지 못하는 경우가 있다는 점을 생각하지 못한게 컸다

 

그래서 최초 dp 배열 초기값을 -1로 하자.

 

x,y지점에서 dp[y][x]가 -1이라는 것은 현재 x,y지점에서 n-1,m-1까지 가는 경우의 수를 모두 세지 않았다는 것이다.

 

그렇다면 dp[y][x] = 0으로 한 다음에, dfs 탐색을 수행한다.

 

하지만 dp[y][x]가 -1이 아니라면 바로 dp[y][x]를 return해준다.

 

from sys import stdin

def dfs(x,y,n,m,maps):
    
    if x == n-1 and y == m-1:

        return 1
    
    else:
        
        if dp[y][x] == -1:
            
            dp[y][x] = 0

            for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
                
                dx = x + ni
                dy = y + nj

                if dx >= 0 and dx <= n-1 and dy >= 0 and dy <= m-1:
                    
                    if maps[y][x] > maps[dy][dx]:
                        
                        dp[y][x] += dfs(dx,dy,n,m,maps)
        
        return dp[y][x]

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

maps = [list(map(int,stdin.readline().split())) for _ in range(m)]

dp = [[-1]*n for _ in range(m)]

dp[0][0] = dfs(0,0,n,m,maps)

print(dp[0][0])