둔필승총

알고리즘 스터디를 진행하다가 접한 문제이다. 음수 간선이 나온다 라는 사실을 어떤 알고리즘으로 풀 수 있었는데.. 이런 생각만 하다가 알고리즘을 찾아보게 되었다.

11657번: 타임머신

최단 거리 알고리즘

최단 거리 알고리즘에는 여러 종류가 있다. 먼저, 제일 먼저 떠오르는 건 다익스트라 알고리즘이다.

다익스트라 알고리즘

다익스트라는 해당 노드에서 출발하여서 다른 노드로 가는 각각의 최단 경로를 구해준다. 그리디 알고리즘을 배우고 접했었는데, 매번 가장 비용이 작은 노드를 선택하기 때문이다.

1. 출발 노드 설정
2. 최단 거리 테이블 초기화 (현재 방문하지 않은 점들은 int(1e9)등으로 설정)
3. 현재 노드와 연결된 노드들 거리 테이블 업데이트
4. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
5. 해당 노드를 거쳐서 다른 노드로 가는 비용을 계산
6. 위의 내요을 반복한다.

다익스트라 알고리즘는 시간복잡도 O(ElogV)로 구현할 수 있다.

여기서 E는 간선의 개수이고, V는 노드의 개수이다.

하지만 다익스트라 알고리즘의 단점은 모든 간선의 가중치가 양수여야 한다는 점이다. 그래서 벨만 포드 알고리즘이 필요하다.

벨만-포드 알고리즘

벨만 포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이라는 내용은 같은데, 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다는 점이 장점이다.

다음과 같은 그래프가 주어졌을 때, 1번에서 3번으로 가는 경우를 생각해보자.

다익스트라의 경우 1번은 2번과 3번이 이어져 있는데, 3번으로 바로 가는게 더 짧기 때문에, 그리디에 의해서 2번은 선택되지 않는다. 그런데 실제로는 1→2→3이 가중치가 14이기 때문에 더 짧다.

따라서, 다익스트라만 이용하면 음수 간선에 대한 처리가 어렵게 된다.

반면, 벨만 포드는 모든 간선을 전부 확인하므로, 최단 거리를 찾을 수 있게 된다.

벨만 - 포드 알고리즘

해당 알고리즘의 과정은 아래의 11657 타임머신 문제를 통해 확인하였다.

[Gold IV] 타임머신 - 11657

[문제 링크]https://www.acmicpc.net/problem/11657

[내가 푼 정답]

import sys

input = sys.stdin.readline


def shortcut(start):
    graph[start] = 0
    for i in range(n):  # 노드 개수만큼 반복
        for j in range(m):
            current_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if graph[current_node] != int(1e9) and graph[next_node] > graph[current_node] + cost:
                graph[next_node] = graph[current_node] + cost
                if i == n - 1:
                    return True
    return False


n, m = map(int, input().split())
graph = [int(1e9)] * (n + 1)
edges = []
for _ in range(m):
    x, y, z = map(int, input().split())
    edges.append((x, y, z))

if shortcut(1):
    print(-1)
else:
    for i in range(2, n + 1):
        if graph[i] == int(1e9):
            print(-1)
        else:
            print(graph[i])

성능 요약

메모리: 32276 KB, 시간: 968 ms

분류

그래프 이론, 벨만–포드

문제 설명

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

내가 푼 풀이

먼저 벨만-포드 알고리즘의 시간 복잡도는 O(VE)이다. 해당 문제에서 V는 500, E는 6000까지 될 수 있으니까 O(30000)은 연산이 1초를 넘지 않아서 사용해도 된다고 판단하였다.

먼저 n,m,edge들을 입력받고, 다익스트라와 비슷하게 그래프를 초기화 해준다.

n, m = map(int, input().split())
graph = [int(1e9)] * (n + 1)
edges = []
for _ in range(m):
    x, y, z = map(int, input().split())
    edges.append((x, y, z))

나는 shortcut이라는 함수를 만들어서 벨만 포드 알고리즘을 진행하였다.

def shortcut(start):
    graph[start] = 0
    for i in range(n):  # 노드 개수만큼 반복
        for j in range(m):
            current_node = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if graph[current_node] != int(1e9) and graph[next_node] > graph[current_node] + cost:
                graph[next_node] = graph[current_node] + cost
                if i == n - 1:
                    return True
    return False

해당 문제에서는 1번 도시만 확인하면 되니까 나중에 start에 1을 넣어서 확인하면 된다.

먼저 시작점은 0으로 초기화해준다.

그리고 노드 개수만큼, edge 개수만큼 이중 for문을 수행해야 한다.

간선을 모두 확인하는데, edges[j]안에 edges의 정보를 current_node, next_node, cost로 다시 받는다.

만약에 현재 노드를 거쳐서 다음 노드로 가는 것이 기존에 시작노드에서 다음노드로 가는 값(graph[next_node])보다 작다면, graph[next_node]를 업데이트 해주면 된다.

여기까지가 벨만-포드의 핵심이다.

이 문제에서는, 해당 반복을 끝냈는데, 가중치가 음수가 되어있는 결과를 확인해야 한다. 왜냐하면 음수가 되었다면, 해당 루트를 계속 반복하면 시간은 거꾸로 간다.(그래서 타임머신 문제이다.)

따라서 노드 개수만큼 반복할 때, 마지막 업데이트를 하는데 또 바뀌어 있다는 뜻은 모든 노드와 간선에 따라서 다 업데이트 했는데 또 바뀌는 것은 해당 가중치가 음수라는 의미이다. 그래서 이 때는 출력을 -1만 하면 된다.

[참고]

https://velog.io/@kimdukbae/알고리즘-벨만-포드-알고리즘-Bellman-Ford-Algorithm