백준 12763:지각하면 안 돼[Python 파이썬 / DFS, 다익스트라 알고리즘]

백준 12763: 지각하면 안 돼

비용과 거리라는 두 가지 조건이 걸리기 때문에 일반적인 다익스트라 알고리즘 문제와는 다른 풀이가 필요했다. 우선 다익스트라로 풀기 전에 DFS로 풀어보자.

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dfs(node, t, c):
    global answer

    if node == N - 1:
        answer = min(answer, c)
        return

    for nxt, time, cost in graph[node]:
        if not visited[nxt]:
            if t + time <= T and c + cost <= M:
                visited[nxt] = True
                dfs(nxt, t + time, c + cost)
                visited[nxt] = False


N = int(input())
T, M = map(int, input().split())
L = int(input())

INF = int(1e9)
graph = [[] for _ in range(N)]

for _ in range(L):
    a, b, time, cost = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, time, cost))
    graph[b].append((a, time, cost))


answer = INF
visited = [False] * N
visited[0] = True
dfs(0, 0, 0)
if answer == INF:
    print(-1)
else:
    print(answer)

DFS로 푸는 것은 그리 어렵지 않다. 문제에서 최소 비용을 물었기 때문에 1번에서 N번까지 가는 경로 중 T시간 이하와 M비용 이하를 충족하는 최소 비용을 답으로 도출해내면 된다.

그래서 1번 노드에서부터 시작하여 연결되어 있는 다음 노드로 가는 시간과 비용을 확인하고, 재귀를 거치며 누적된 시간과 비용이 T이하, M이하인지 조건문으로 확인만 하면 된다. 방문처리는 당연히 해준다. DFS로 풀었을 때는 골드2의 난이도로 느껴지지는 않았다.

이제 다익스트라 알고리즘으로 접근해보자.

from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N = int(input())
T, M = map(int, input().split())
L = int(input())

INF = int(1e9)
graph = [[] for _ in range(N + 1)]

for _ in range(L):
    a, b, time, cost = map(int, input().split())
    graph[a].append((b, time, cost))
    graph[b].append((a, time, cost))

distcost = [[INF for _ in range(10000 + 1)] for _ in range(N + 1)]
distcost[1][0] = 0

q = [(0, 0, 1)]
while q:
    time, cost, now = heappop(q)
    if distcost[now][cost] < time:
        continue
    for nxt, n_t, n_c in graph[now]:
        tt, tc = time + n_t, cost + n_c
        if tt <= T and tc <= M:
            if tt < distcost[nxt][tc]:
                distcost[nxt][tc] = tt
                heappush(q, (tt, tc, nxt))

for i in range(M + 1):
    if distcost[N][i] <= T:
        print(i)
        sys.exit()
print(-1)

최단 거리만을 찾는 일반적인 다익스트라 문제와 달리 'M 이하의 비용'이라는 조건이 추가되었기 때문에 2차원 배열로 해결한다. '특정 비용에서의 최단시간' 를 기록하는 것이다.

일단 이 2차원 배열은 모두 무한대로 초기화해주고, 우선순위 큐를 활용하여 경로를 거쳐가며 누적된 시간, 비용을 이전에 기록해놓은 특정 비용에서의 최단시간과 비교한다. (이 특정 비용은 큐에서 pop된 누적된 비용이다)

그리고 마지막으로 1번에서 N번으로 가는 경로들(distcost[N]) 중 0부터 M까지의 인덱스를 순차적으로 확인하여 T 이하의 시간이 걸리는 경우의 수가 있으면 바로 답을 출력해낸다. (비용 최소값을 출력해야 하기 때문)

2차원 배열 메모이제이션은 가끔씩 DP나 BFS 문제에도 등장하는 풀이법이라 잘 기억해놓는 게 좋을 것 같다. 이런 식의 문제를 맞닥뜨릴 때마다 이상하게 기억이 안 난다..