BOJ #10217 KCM Travel

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

문제 링크

BOJ #10217 KCM Travel

문제 풀이

시간 제약이 굉장히 빡빡했던 문제였다. 이 문제 때문에 Python 함수 코드가 일반 코드보다 빠른 이유 포스팅을 작성했었다. 우선 다익스트라로 풀긴 푸는데 비용 제약이 추가되었음을 확인될 수 있다. 따라서 단순히 시간이 빠르다고 경로를 채택했다간 나중에는 비용제약으로 경로 없음을 출력하는 오류가 발생할 여지가 있으나 조금 다르게 생각해야 한다.

다익스트라 알고리즘으로 특정 비용을 써서 임의의 정점까지 최단 거리로 간다고 할 때 그 이후의 비용에 대해서도 전부 해당 경로를 이용하게 될 것이다. 이 점을 이용해보자.

• [정점][비용]의 2차월 배열 생성
• 모든 주소를 INF로 초기화하되 [i][i]는 0으로 설정
• q를 선언하고 안에 (시간, 비용, 정점)을 입력, 초기값은 (0, 0, 1)이 되겠다.
• q가 값을 갖는 동안 popleft하여 시간, 비용, 탐색할 정점을 꺼낸다.
• 만약 [정점][비용]이 꺼낸 시간보다 작으면 의미 없는 탐색이므로 다음 순회로 넘어간다.
• 그게 아니면 탐색할 정점에 연결된 간선들에 대해 현재 시간과 비용에 간선의 시간과 비용을 더한다. 만약 간선의 비용을 더한 결과가 M이하거나 [간선의 도착지][신규 비용]의 소요시간과 비교했을 때 더 작다면 의미있는 탐색이므로 q에 더한다. (신규 시간, 신규 비용, 신규 도착지)
• q에 위 item을 더하기 전 조건문에서 기존 값과 비교를 한 뒤 더 작은 값임을 확인받았다. 따라서, 이후 cost에 대해 그보다 더 작은 값이 나올 때까지 신규 시간으로 바꿔주면 된다.
• 모든 탐색이 종료된 후 [정점][주어진 비용]은 주어진 비용 내에서 도착지까지 갈 수 있는 최소 시간이다.
• 갱신되지 않아 INF면 최단 경로가 존재하지 않음을 의미하고 그렇지 않다면 그대로 출력한다.

참고로 해당 로직을 함수 안에 넣고 실행하면 통과하나 그렇지 않으면 시간 초과를 출력한다. 원인에 대해 찾아본 결과를 나름대로 Python 함수 코드가 일반 코드보다 빠른 이유에 정리하였다.

python 코드

import sys
from collections import deque
input = sys.stdin.readline

def solve():
    INF = float('inf')
    for _ in range(int(input())):
        N, M, K = map(int, input().split())
    edges = [[] for _ in range(N + 1)]
    for _ in range(K):
        u, v, c, d = map(int, input().split())
        edges[u].append((v, c, d))
    dist = [[INF] * (M + 1) for _ in range(N + 1)]
    q = deque()
    q.append((0, 0, 1))
    while q:
        time, cost, node = q.popleft()
        if time > dist[node][cost]:
            continue
        for city, c, t in edges[node]:
            alt_t, alt_c = time + t, cost + c
            if alt_c <= M and alt_t < dist[city][alt_c]:
                for i in range(alt_c, M + 1):
                    if alt_t < dist[city][i]:
                        dist[city][i] = alt_t
                    else:
                        break
                q.append((alt_t, alt_c, city))
    s = dist[N][M]
    if s == INF:
        print("Poor KCM")
    else:
        print(s)

solve()