[파이썬/python] 백준 - 1513 경로 찾기

문제

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

---

문제 설명

1. N*M 크기의 직사각형 도시가 존재한다.
2. 세준이의 집은 (1,1)에 있고, 학원은 (N,M)에 있고, 오락실은 C개 있다.
   1. 집에서 학원까지 이동해야 한다. 
   2. 이 때 오락실은 (1,1) 혹은 (N,M)에 존재할 수 있다.
3. 현재 위치가 (r,c)일 때 (r+1, c) 혹은 (r, c+1)로 이동이 가능하다.
   1. 이 때 오락실을 방문한다면 오락실 번호가 증가하는 순서대로 방문해야 한다.
      1번 -> 2번 -> 3번 : 가능
      2번 -> 1번 : 불가능
4. 오락실을 0번부터 C번 방문했을 때 까지의 모든 경우의 수를 출력한다.

 

---

풀이

세준이는 현재 위치를 기준으로 r이 증가하거나, c가 증가하는 방향으로만 이동한다.

 

그럴 경우에 학원에 도착하는 경우의 수를 모두 구하는 것이 이 문제의 포인트이다.

 

start에서 end 지점까지 걸리는 cost들을 모두 구하는 문제이기 때문에 이는 bfs 혹은 dfs와 같은 그래프 탐색으로 생각할 수 있겠다.

 

하지만 처음에 말했던 대로 증가하는 방향으로만 이동하기 때문에 사이클이 존재할 수 없다. 이 말은 즉 이전 값을 누적하면서 다음 값을 경신한다는 말이다.

 

그렇다면 우리는 다이나믹 프로그래밍을 생각해 볼 수 있다. 이 문제를 그래프로 빗대어 보면 모든 간선은 한 방향, 즉 방향성이 존재하고 사이클이 없다. 따라서 DAG(Directed Acyclic Graph) 형태를 띠고 있기 때문에 DP 알고리즘을 통해 최단경로를 계산할 수 있다는 의미이다.

 

따라서 나는 DP 알고리즘을 통해 문제를 풀이했다. DP는 하나의 문제를 여러 부분문제로 나누어서 점화식을 통해 반복적인 계산을 피해야 한다.

 

문제의 점화식은 다음과 같이 세울 수 있다.

DP[R][C][현재 오락실 번호][현재 방문한 오락실의 개수]

 

(r,c)의 위치에서 K번 오락실에 도달했을 때 각각 몇 번째로 K번 오락실에 방문했는가로 이해할 수 있다.

 

예시를 통해 이해해 보자.

 

먼저 시작지점에 대해 초기화를 진행한다.

 

만약 시작지점에 오락실이 없다면, 개수가 0개인 오락실을 방문했으므로 dp[0][0][0][0] = 1로 초기화한다.

 

시작지점에 오락실이 존재한다면, 개수가 1개인 오락실을 방문했으므로 dp[0][0][k][1] = 1로 초기화한다.

 

다음 위치를 갱신할 때는 두 가지의 경우로 나누어 계산한다.

1. 이동할 위치에 오락실이 없을 때
   현재 위치에 오락실이 존재하지 않는다면, 이전 위치들에서 현재 위치로 이동한다고 하더라도 오락실의 개수는 변하지 않는다.
   따라서 이전 dp [r][c]가 가지고 있는 모든 dp [r][c][k][z]의 값들을 현재 위치에 더해준다.
   
   
2. 이동할 위치에 오락실이 있을 때
   이 부분을 이해하기 위해 예시를 들어보겠다. 현재의 위치를 (r, c)라고 하고, 직전의 위치를 (nr, nc)라고 가정하겠다.
   • 현재 위치가 dp[r][c][3][1]이라면, 현재 방문한 오락실의 개수가 1이라는 의미이다.
     그러므로 이전 좌표들에서 방문한 오락실의 개수가 0인 위치들의 값을 더해줘야 한다.
     → dp[r][c][3][1] += dp[nr][nc][0][0]
     
     
   • 현재 위치가 dp[r][c][3][2]라면,
     → dp[r][c][3][2] += (dp[nr][nc][1][1] + dp[nr][nc][2][1])
     
     
   • 현재 위치가 dp[r][c][3][3]이라면,
     → dp[r][c][3][2] += dp[nr][nc][2][1]

즉, 현재 방문한 오락실의 개수 - 1인 지점들의 값을 더해주면 된다.

 

이를 일반화시켜보면, dp[r][c][k][z]일 때 k가 (z-1~k-1)인 값을 전부 더해주는 것과 같다.
따라서 dp[r][c][k][z] += dp[nr][nc][t][z-1]을 진행하여 값을 갱신한다.

 

최종적으로 도착지점인 dp[-1][-1] 위치에서 모든 dp[-1][-1][i][j]가 가지는 값들을 더해서 결과를 출력한다.

 

---

코드

import sys
input = sys.stdin.readline

dr = [-1,0]
dc = [0,-1]
MOD = 1000007
N,M,C = map(int,input().split())

board = [[0 for _ in range(M)] for _ in range(N)]

for i in range(1,C+1):
    r,c = map(int,input().split())
    board[r-1][c-1] = i


dp = [[[[0 for _ in range(C+1)] for _ in range(C+1)] for _ in range(M)] for _ in range(N)]

if board[0][0] == 0:
    dp[0][0][board[0][0]][0] = 1
else:
    dp[0][0][board[0][0]][1] = 1



for r in range(N):
    for c in range(M):
        if (r,c) == (0,0):
            continue

        for i in range(2):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or nr > N-1 or nc < 0 or nc > M-1:
                continue

            if board[r][c] == 0:
                for k in range(C+1):
                    for t in range(C+1):
                        dp[r][c][k][t] = (dp[r][c][k][t] + dp[nr][nc][k][t]) % MOD
            else:
                k = board[r][c]
                for z in range(1,k+1):
                    for t in range(z-1,k):
                        dp[r][c][k][z] = (dp[r][c][k][z] + dp[nr][nc][t][z-1]) % MOD
                        
res = [0 for _ in range(C+1)]
for i in range(C+1):
    for j in range(C+1):
        res[j] = (res[j]+ dp[-1][-1][i][j]) % MOD
print(*res)

---

시간복잡도

• 4차 반복문에서 $O(R*C*C*C)$ 만큼의 연산을 수행한다.
• 최악의 경우 R = 50, C = 50, C = 50, C = 50이므로 약 $O(6*10^6)$정도의 시간복잡도를 가진다.