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

 

 

문제 링크

 

https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

 

문제 풀이

 

음의 가중치가 존재하는 그래프 문제이므로 다익스트라보다는 벨만 포드를 사용해야합니다.

이 문제는 벨만 포드 알고리즘의 기초 개념만을 담은 문제입니다.

 

한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

 

문제에서는 1번 노드에서 출발한다는 조건이 없습니다.

모든 지점에서 출발이 가능하며 해당 지점으로 돌아왔을 때 가중치가 줄어드는 경우가 있는지를 묻고 있습니다.

이는 결국 음의 사이클이 존재하는지를 묻는 문제입니다.

 

def bellmanFord(start):
    distance[start] = 0
    for i in range(1, n + 1):
        for j in range(len(edges)):
            now, next, cost = edges[j]
            if distance[now] + cost < distance[next]:
                distance[next] = distance[now] + cost
                if i == n:
                    return True
    return False

 

위 코드와 같이 벨만포드 알고리즘을 작성할 수 있습니다.

특정 지점을 거쳐서 갈 때 거리가 짧을 경우 값을 갱신시켜준다는 점은 다익스트라와 같지만,

벨만포드에서는 모든 노드에 대해 검사를 하고서도 최솟값이 갱신될 경우 음의 사이클이 존재함을 판단할 수 있습니다.

 

 

주의해야 할 점은 도로의 경우 양방향 간선이며, 웜홀은 단방향 간선입니다.

 

전체 코드

 

def bellmanFord(start):
    distance[start] = 0
    for i in range(1, n + 1):
        for j in range(len(edges)):
            now, next, cost = edges[j]
            if distance[now] + cost < distance[next]:
                distance[next] = distance[now] + cost
                if i == n:
                    return True
    return False

TC = int(input())
for _ in range(TC):
    # n : 지점 수, m : 도로 수, w : 웜홀 수
    n, m, w = map(int, input().split())
    edges = []
    distance = [10001] * (n + 1)
    for _ in range(m):  # 도로
        s, e, t = map(int, input().split())
        edges.append((s, e, t))
        edges.append((e, s, t))
    for _ in range(w):  # 웜홀
        s, e, t = map(int, input().split())
        edges.append((s, e, -t))
    if bellmanFord(1):
        print("YES")
    else:
        print("NO")