[백준] 1865 파이썬

문제

---

• 백준 1865 (골드 3)

백준 1865

처음 읽었을 때는 문제가 잘 이해가 가지 않았는데 입력 변수들을 처리하다보니 이해가 갔다.
음의 가중치가 있는 그래프를 처리해야 하는 문제였다.
어떻게 풀어야 하는지 감이 잘 잡히지 않아서 벨만-포드 알고리즘을 찾아보았다.

벨만-포드 알고리즘

---

• 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘
• 다익스트라 알고리즘과는 다르게 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다는 것이 특징이다.
• 그렇지만 벨만-포드 알고리즘의 시간 복잡도는 O(VE)로 O((V+E)lgV)인 다익스트라 알고리즘보다 일반적으로 느리다.
• 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나가는 방식으로 진행한다.
• 파이썬으로 나타낸 코드는 아래와 같다.

def bellman_ford(st):
    dist[st] = 0
    for i in range(v):
        for j in range(e):
            current, next, edge_cost = edges[j]
            if dist[current] != INF and dist[next] > dist[current] + edge_cost:
                dist[next] = dist[current] + edge_cost
                if i == v - 1:
                    return True

    return False

내 코드

---

모든 노드를 시작점으로 잡아서 벨만-포드 알고리즘을 수행하였더니 시간초과가 발생했다.
음수 사이클이 그래프에 존재하면 그래프 내부에서 어떤한 경로든 음수 가중치로 이동 가능하다는 것을 알고 한번만 수행하면 구할 수 있다는 것을 알게 되고 코드를 수정하였다.

import sys
input = sys.stdin.readline

def bellman_ford():
    for i in range(n):
        for j in range(len(road)):
            s, e, t = road[j]
            if dist[e] > dist[s] + t:
                dist[e] = dist[s] + t
                if i == n - 1:
                    return True
    return False

tc = int(input())
for _ in range(tc):
    n, m, w = map(int, input().split())
    road = []
    dist = [1e9] * (n + 1)

    for _ in range(m):
        s, e, t = map(int, input().split())
        road.append((s, e, t))
        road.append((e, s, t))

    for _ in range(w):
        s, e, t = map(int, input().split())
        road.append((s, e, (-1) * t))

    if bellman_ford():
        print("YES")
    else:
        print("NO")

음수 가중치를 사용하는 그래프 문제에서 벨만-포드 알고리즘을 잘 활용해봐야겠다.