[파이썬/python] 백준 - 2157 여행

문제

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

---

문제 설명

1. 1번부터 N번까지 도시가 존재한다.
2. 이 중 M개 이하의 도시를 여행해야 한다.
   1. 여행 경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝내야한다.
   2. 1번과 N번 도시도 M개의 도시에 포함된다.
   3. 무조건 번호가 증가하는 도시로만 이동이 가능하다.
3. 먹게 되는 기내식의 점수의 총 합의 최댓값을 구한다.

---

풀이

처음에는 DFS로 접근했지만, 나올 수 있는 경우의 수가 300!(N은 최대 300)이기 때문에 시간초과가 발생했다.

그래서 다이나믹 프로그래밍을 통해 문제를 풀이했다. 이 문제의 핵심은 바로 M에 존재한다.

 

1과 2 노드에서 각각 3으로 이동하고 M = 3이라고 가정하자.

1 -> 3일 때 도시를 지난 횟수는 3개이고, cost = 10이다.

2 -> 3일 때 도시를 지난 횟수는 2개이고, cost = 5이다.

 

평소처럼 DP를 구현했다면 3으로 도착했을 때 최대 코스트인 1->3, cost = 10을 선택했을 것이다.

하지만 2 -> 3으로 이동한다면 한 개의 도시를 더 이동할 수 있기 때문에, 더 큰 cost를 더할 수 있다면 문제의 반례가 된다.

 

그래서 배열의 크기를 m개만큼 잡아 각 도시 개수를 카운트하면서 cost를 갱신해서 결과를 구했다.

  

1. cost 배열에 v1에서 v2로 이동할 때 cost를 갱신한다.
   1. 이 때 오름차순으로이동하기 때문에 v1이 v2보다 크다면 갱신하지 않는다.
2. dp 배열을 -1로 갱신한다.
   1. dp 배열을 0으로 초기화 하게 되면 1에서 이동하지 않은 노드 또한 갱신하게 될 가능성이 존재하기 때문에, 예외를 처리한다.
   2.    이 때 1번 노드는 0으로 갱신한다.
3. 이동 가능한 모든 좌표를 탐색하며, cnt가 1부터 m까지 나올 수 있는 cost를 갱신한다. 
4. N번 도시일때 cost를 출력한다.  

---

코드

import sys
input = sys.stdin.readline
n,m,k = map(int,input().split())

cost = [[-1 for _ in range(n+1)] for _ in range(n+1)]
pos = {}
for _ in range(k):
    v1,v2,c = map(int,input().split())
    if v1 > v2:
        continue
    cost[v1][v2] = max(cost[v1][v2],c)

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

for i in range(m+1):
    dp[1][i] = 0
    
for v1 in range(1, n+1):
    for v2 in range(v1+1,n+1):
        if cost[v1][v2] == -1:
            continue
        for cnt in range(1,m):
            if dp[v1][cnt] == -1:
                continue
            dp[v2][cnt+1] = max(dp[v2][cnt+1], dp[v1][cnt] + cost[v1][v2])
print(max(dp[n]))

---

시간복잡도

• 최악의 경우 N = 300이다.
• 단순 계산하면 약 $O(100^3) = O(10^6)$이지만, 갈 수 없는 좌표를 continue하기 때문에, 이 보다 더 적은 시간이 소요될 것이라 생각한다.