[파이썬] 1865 웜홀 (백준)

1. 문제 설명

문제 : 1865 - 웜홀 https://www.acmicpc.net/problem/1865 (골3)

사용 언어 : 파이썬 (Pypy3)

사용 알고리즘 : 벨만-포드 알고리즘

 

문제요약 :

M개의 양방향 간선인 도로와 W개의 단방향 간선인 웜홀이 이들을 지나는 시간과 함께 주어졌을 때, 음의 사이클이 있는지 구하여라.

 

---

2. 문제 풀이

해설 :

음의 사이클을 찾을 수 있는 벨만포드 알고리즘을 이용한다.

여기서 주의해야 할 점이 있는데, 일반 벨만포드 코드와 다르게 아래 코드를 삭제해야 한다.

distance[now_node] != INF

 

왜냐하면 위 코드는 'start'라는 지점에서부터 연결된 각 노드까지의 최단 경로를 구하는 코드이다. 하지만 이 문제에서는 시작 지점이 주어지지 않고, 음의 간선이 있는지의 여부만 판단하면 되기 때문에 임의의 한 노드만 시작지점으로 두어 위 코드를 삭제한다.

 

코드 :

import sys; input = sys.stdin.readline

INF = int(1e9)

def BellmanFord(start):
    distance = [INF]*(N+1)
    distance[start] = 0

    for i in range(N):
        for j in range(2*M+W):
            now_node, next_node, cost = roads[j]

            if distance[now_node] + cost < distance[next_node]:
                distance[next_node] = distance[now_node] + cost

                if i == N-1: return True

    return False

ans = []

TC = int(input())
for _ in range(TC):
    N, M, W = map(int,input().split())

    roads = []
    for i in range(M):
        S, E, T = map(int,input().split())
        roads.append([S, E, T])
        roads.append([E, S, T])

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

    if BellmanFord(1): ans.append('YES')
    else: ans.append('NO')

print('\n'.join(ans))

---

앞으로 코딩과 알고리즘 관련 글을 업로드할 예정입니다!

아직 배우는 중이라서 부족한 점이 있으면 댓글 남겨주시면 감사하겠습니다!!