알고리즘 스터디 - 백준 1865번 : 웜홀

문제 해석

• 월드나라에 N개의 지점 사이에 M개의 도로와 W개의 웜홀이 존재
• 도로는 방향이 없고 웜홀은 방향이 있다.
• 시작 위치에서 도착 위치로 가는 웜홀을 사용하면 시간이 뒤로 가게 된다.

한 지점에서 출발을 해서 다시 출발하였던 위치로 왔을 때보다 시간이 되돌아가는 경우가 있는지 확인

어떤 알고리즘을 써야할까?

그래프의 특성을 살펴보면 시간이 줄어드는 음수의 경우가 나타나게 된다. 이 경우에는 벨만 포드 알고리즘을 사용해야 한다.

벨만 포드 알고리즘 프로세스

1. 시작 정점을 결정한다.
2. 시작 정점에서 각각 다른 정점까지의 거리 값을 무한대로 초기화한다.
3. 현재 정점에서 모든 인접 정점들을 탐색하며, 기존에 저자오디어 있는 인접 정점까지의 거리 보다 현재 정점을 거쳐 인접 정점에 도달하는 거리가 더 짧을 경우 짧은 거리로 갱신해준다.
4. 3번의 과정을 정점의 개수만큼 반복한다.
5. 이 과정을 마치고 나서 거리가 갱신되는 경우가 생기면 그래프에 음수 사이클이 존재하는 것이다.

기본 형태

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []
        self.nodes = []
        
    def add_edge(self, s, d, w):
        self.graph.append([s, d, w])
    
    def addNode(self, value):
        self.nodes.append(value)
    
    def print_solution(self, dist):
        print("Distance of Vertex from Source")
        for key, value in dist.items():
            print('  ' + key, ' :   ', value)
    
    def bellmanFord(self, src):
        dist = {i: float("Inf") for i in self.nodes}
        dist[src] = 0
        
        for temp in range(self.V-1):
            for s, d, w in self.graph:
                if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                    dist[d] = dist[s] + w
        
        for s, d, w in self.graph:
            if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                print("Graph contanins negative cycle")
                return
        
        self.print_solution(dist)

g = Graph(5)
g.addNode("A")
g.addNode("B")
g.addNode("C")
g.addNode("D")
g.addNode("E")
g.add_edge("A", "C", 6)
g.add_edge("A", "D", 6)
g.add_edge("B", "A", 3)
g.add_edge("C", "D", 1)
g.add_edge("D", "C", 2)
g.add_edge("D", "B", 1)
g.add_edge("E", "B", 4)
g.add_edge("E", "D", 2)
g.bellmanFord("E")

알고리즘 코드

from dis import dis
import sys
input = sys.stdin.readline
INF = sys.maxsize

def bellmanFord():
    dist = {i: INF for i in range(1, N+1)}

    for i in range(1, N+1):
        for j in range(1, N+1):
            for w, d in edges[j]:
                if dist[d] > w + dist[j]:
                    dist[d] = w + dist[j]
                    if i == N:
                        return "YES"
    return "NO"

TC = int(input())
for _ in range(TC):
    N, M, W =  map(int, input().split())
    edges = [[] for _ in range(N+1)]

    for _ in range(M):
        S, E, T = map(int, input().split())
        edges[S].append((T, E))
        edges[E].append((T, S))
    
    for _ in range(W):
        S, E, T = map(int, input().split())
        edges[S].append((-T, E))

    print(bellmanFord())