[BOJ]11657. 타임머신

11657. 타임머신

❌code1

import sys


def bellman_ford():
    dist = [10000 * N] * (N + 1)  # 걸리는 시간 기록
    dist[1] = 0  # 출발 도시 초기화

    # N회 반복하여 모든 간선을 탐색해 최소 시간 기록
    for repeat in range(1, N + 1):
        for current_node, next_node, cost in edges:
            if dist[current_node] + cost < dist[next_node]:
                dist[next_node] = dist[current_node] + cost

                # N회 반복에 경로가 또 갱신된다면 무한히 도는 음수 사이클 존재
                if repeat == N:
                    return False
    return dist


N, M = map(int, sys.stdin.readline().split())
edges = []  # 간선 저장 배열

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    edges.append([A, B, C])

result = bellman_ford()
if result:
    for city in range(1, N + 1):
        if city == 1:
            continue
        if result[city] == 10000 * N:
            print(-1)
        else:
            print(result[city])
else:
    print(-1)

시도

벨만-포드 알고리즘을 이용해 1번 노드에서 각 노드로 가기 위해 걸리는 시간을 기록한다. 알고리즘 구현은 링크를 참고하였다.

문제

최소시간을 갱신할 때 한 번도 방문하지 않은 정점까지 고려하면 문제가 생긴다. 극단적으로 다음의 예시가 있다.

4 1
2 4 -1

answer
-1
-1
-1

wrong
-1
-1
39999

4개의 정점이 존재하며 2번에서 4번 정점으로 갈 때 -1의 시간이 소요되는 경우 1번 정점에서 갈 수 있는 정점은 존재하지 않는다. 하지만 code1에선 2 4 -1 간선을 고려하여 1번에서 4번 정점으로 갈 때 39999의 시간이 소요된다고 말한다. 따라서 방문한 적 없는 정점은 갱신되어선 안 된다.

이는 또한 간선 탐색을 N번 반복하는 것과 연결되어 있다. 간선을 탐색할 때는 항상 모든 간선을 탐색하지 않으며, 매번 방문 가능한 정점이 갱신될 수 있다. 현재 방문 불가능한 정점이 다음 반복에선 가능할 수도 있는 상황이 생기기 때문에 1번 정점에서 방문 가능한 정점을 모두 방문하기 위해 간선 탐색을 반복해야 한다.

⭕code2

import sys


def bellman_ford():
    dist = [10000 * N] * (N + 1)  # 걸리는 시간 기록
    dist[1] = 0  # 출발 도시 초기화

    # N회 반복하여 모든 간선을 탐색해 최소 시간 기록
    for repeat in range(1, N + 1):
        for current_node, next_node, cost in edges:
            # 한번도 간 적 없는 노드는 넘어감
            if dist[current_node] == 10000 * N:
                continue

            if dist[current_node] + cost < dist[next_node]:
                dist[next_node] = dist[current_node] + cost

                # N회 반복에 경로가 또 갱신된다면 무한히 도는 음수 사이클 존재
                if repeat == N:
                    return False
    return dist


N, M = map(int, sys.stdin.readline().split())
edges = []  # 간선 저장 배열

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    edges.append([A, B, C])

result = bellman_ford()
if result:
    for city in range(1, N + 1):
        if city == 1:
            continue
        if result[city] == 10000 * N:
            print(-1)
        else:
            print(result[city])
else:
    print(-1)

시도

이전에 방문한 적 없는 정점 즉, 걸리는 시간이 10000 * N에서 바뀌지 않은 정점은 간선 탐색 시 고려하지 않는다.

요약

벨만-포드 알고리즘을 사용할 때에는 한 번도 방문하지 않은 정점을 간선 탐색 시 고려해서는 안 된다.