백준 11657번 Bellman-Ford

서론

11657번: 타임머신

기본적인 그래프를 탐색하는 문제이지만 이번에는 그래프 내의 가중치에 음수값이 있습니다. 이때는 Dijkstra 알고리즘을 사용할 수 없습니다. Bellman-Ford라는 알고리즘을 사용해야 하는데 몰랐던 개념이기 때문에 학습을 하고 풀었더니 맞았습니다.

제한 조건

• 시간제한 - 1초

시간제한은 1초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. Bellman-Ford 알고리즘은 V-1 번 만큼 Edge relaxation을 하므로 O(VE)의 시간 복잡도를 가지고, 문제의 조건에서 V=500, E=6,000이니 충분합니다.

• 메모리 제한 - 256MB

메모리 제한은 256MB입니다. 그래프를 탐색하는 문제를 풀다 보니 기본적으로 그래프 자체를 선언하거나, 일반적으로 사용하는 visited나 dist_list, DP 등을 선언하는 데는 메모리 제한이 크게 문제가 되지 않습니다. 또 Bellman-Ford 알고리즘은 Dijkstra에서 사용하는 힙같은 다른 자료구조를 사용하지 않고 for 문만을 돌리기 때문에 메모리 제한은 충분합니다.

Bellman-Ford

시작정점을 기준으로 모든 정점까지의 최단 거리를 구해야 하는 문제이지만 가중치에 음수가 있습니다. 따라서 Dijkstra를 사용하지 못하고, Bellman-Ford를 사용해야 합니다.

여기서 edge relaxation이라는 개념이 등장하는데 이것은 모든 edge 정보를 가지고 도착정점의 최단 거리가 시작정점+weight의 값보다 작으면 도착정점의 최단 거리를 갱신하는 것입니다. 코드로 보는게 더 쉬울 것 같습니다. 시작 정점에서의 최단 거리를 담고있는 최단거리 리스트를 사용합니다.(dist_list[vertex_num]).전체적인 Bellman-Ford의 흐름은 아래와 같습니다.

1. edge relaxation을 하기 위해서 시작정점의 최단 거리를 0으로 설정합니다.
2. 최단 거리가 갱신된 정점에서만 edge relaxation을 합니다.
3. 1-2 과정을 vertex_num-1번 수행합니다.
4. 만약 vertex_num-1번 한 후의 최단 거리와 vertex_num번 한 후의 최단 거리가 다르다면 이것은 사용한 graph가 negative-loop을 가진단 뜻입니다.

문제에서도 negative-loop가 있는지 찾아야 했기 때문에 edge relaxation을 vertex_num-1번한 후의 최단 거리와 vertex_num한 후의 그래프를 저장하여 비교하였습니다. 전체코드는 아래와 같습니다.

import sys
input = sys.stdin.readline

vertex_num, edge_num = map(int, input().split())
dist_list = [sys.maxsize] * (vertex_num+1)
dist_list[1] = 0


def make_edge():
    edge_list = []
    for i in range(edge_num):
        start, end, weight = map(int, input().split())
        edge_list.append([start, end, weight])
    return edge_list


def Bellman_Ford(edge_list):
    negative_loop = []
    for i in range(vertex_num):
        for edge in edge_list:
            start, end, weight = edge
            if dist_list[start] != sys.maxsize:
                dist_list[end] = min(dist_list[start]+weight,  dist_list[end])
        if i == vertex_num-2:
            negative_loop.append(dist_list[:])
        if i == vertex_num-1:
            negative_loop.append(dist_list[:])
    return negative_loop


edge_list = make_edge()
negative_loop = Bellman_Ford(edge_list)

if negative_loop[0] == negative_loop[1]:
    for i in negative_loop[1][2:]:
        if i == sys.maxsize:
            print(-1)
        else:
            print(i)
else:
    print(-1)

생각

처음에는 왜 edge-relaxation을 vertex_num-1번 해야 하는가를 이해하지 못했지만 간단하게 생각하면 vertex 간의 가장 많이 떨어진 거리가 vertex_num-1이기 때문입니다. 따라서 vertex_num-1번 수행하게 되면 가장 많이 떨어진 거리의 vertex도 update 되게 됩니다.