(백준) 타임머신 11657

알고리즘 스터디를 진행하면서 만난 문제입니다.

알고리즘을 사용하여 음의 에지가 발생한다는 사실을 해결할 수 있었습니다.

도시의 수 N(1 ≤ N ≤ 500)과 버스 노선의 수 M(1 ≤ M ≤ 6,000)이 첫 번째 줄에 주어집니다.

두 번째 라인부터 M 라인에는 버스 노선 정보 A, B, C(1≤A, B≤N, -10,000≤C≤10,000)가 주어진다.

www.acmicpc.net

쉬운 목차

최단 거리 알고리즘

최단 거리 알고리즘에는 다양한 유형이 있습니다.

가장 먼저 떠오르는 것은 Dijkstra의 알고리즘입니다.

다익스트라 알고리즘

Dijkstra는 한 노드에서 다른 노드로의 모든 최단 경로를 찾습니다.

매번 비용이 가장 저렴한 노드를 선택하기 때문에 그리디 알고리즘을 알게 되었습니다.

시작 노드 설정
최단 거리 테이블 초기화(현재 방문하지 않은 지점은 int(1e9) 등으로 설정)
현재 노드에 연결된 노드의 거리 테이블 업데이트
미방문 노드 중 거리가 가장 짧은 노드 선택
이 노드를 통해 다른 노드로 이동하는 비용 계산
위의 요약을 반복하십시오.

Dijkstra 알고리즘은 O(ElogV)의 시간 복잡도로 구현될 수 있습니다.

여기서 E는 모서리의 수이고 V는 정점의 수입니다.

그러나 Dijkstra 알고리즘의 단점은 모든 간선 가중치가 양수여야 한다는 것입니다.

따라서 Bellman-Ford 알고리즘이 필요합니다.

벨만-포드 알고리즘

Bellman-Ford 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 찾는 알고리즘이지만 Edge 가중치가 음수인 경우에도 최단 거리를 찾을 수 있다는 장점이 있습니다.

다음 다이어그램을 사용하여 1단계에서 3단계로 이동하는 경우를 고려하십시오.

Dijkstra의 경우 1번은 2번과 3번이 연결되어 있지만 3번으로 가는 직행 경로가 더 짧기 때문에 2번은 Greedy가 선택하지 않습니다.

그러나 실제로는 가중치가 14이므로 1→2→3이 더 짧습니다.

따라서 Dijkstra만 사용하면 음의 모서리를 처리하기가 어렵습니다.

반면에 Bellman Ford는 최단 거리를 찾기 위해 모든 모서리를 검사합니다.

벨만-포드 알고리즘

알고리즘의 과정은 아래의 11657 타임머신 문제로 검증되었습니다.

(골드 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))

성능 요약

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

분류

그래프 이론, Bellman-Ford

문제 설명

N개의 도시가 있습니다.

그리고 한 도시에서 출발하여 다른 도시에 도착하는 M-버스가 있습니다.

각 버스는 A, B, C로 나타낼 수 있으며, 여기서 A는 출발 도시, B는 목적지 도시, C는 버스 운행 시간입니다.

시간 C가 양수가 아닌 경우가 있습니다.

C = 0은 텔레포트를 의미하고, C < 0은 타임머신을 이용한 시간 여행을 의미합니다.

도시 1에서 다음 도시까지 가장 빠른 시간을 찾는 프로그램을 작성하십시오.

기입

누르다

도시 1에서 시작하여 특정 도시까지 시간을 무한히 거꾸로 되돌릴 수 있으면 첫 번째 줄에 -1을 인쇄하십시오. 그렇지 않으면 1번 도시에서 2번 도시, 3번 도시, …, N번 도시로 가는 가장 빠른 시간이 N-1행에 걸쳐 각 행에 순차적으로 인쇄된다.

해당 도시로 가는 경로가 없으면 대신 -1을 반환합니다.

내가 풀었던 수수께끼

먼저 Bellman-Ford 알고리즘의 시간복잡도는 O(VE)이다.

이 문제에서 V는 500까지, E는 6000까지 가능하므로 O(30000) 연산이 1초를 넘지 않기 때문에 사용할 수 있다고 판단했다.

먼저 n, m 및 모서리를 입력하고 Dijkstra와 유사하게 그래프를 초기화합니다.

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))

Bellman-Ford 알고리즘을 진행하기 위해 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으로 초기화됩니다.

또한 중복 for 문이 있는 만큼 노드와 엣지를 실행해야 합니다.

모든 edge를 확인하고 edge 정보를 다시 current_node, next_node, cost in edge(j)로 수신한다.

현재 노드를 통해 다음 노드로 이동하는 것이 시작 노드에서 다음 노드까지 이전 값(graph(next_node))보다 작으면 그래프(next_node)를 업데이트할 수 있습니다.

이것이 Bellman-Ford의 본질입니다.

이 문제에서는 이 반복을 마쳤으며 가중치가 음수일 때 결과를 확인해야 합니다.

음수이고 이 경로를 계속해서 반복하면 시간이 거꾸로 흐르기 때문입니다(따라서 타임머신 문제).

따라서 노드 수만큼 노드가 반복되면 마지막 업데이트를 수행하고 변경은 모든 노드와 에지가 업데이트되었음을 의미하지만 차례로 변경은 해당 가중치가 음수임을 의미합니다.

따라서 이 경우 -1만 출력하면 됩니다.

(참조)

https://velog.io/@kimdukbae/algorithm-bellman-ford-algorithm-Bellman-Ford-Algorithm