[Baekjoon Online Judge] 백준 1865번 웜홀(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1865번 웜홀

(Python)

(글쓴날 : 2020.06.15)

 

---

* Baekjoon Online Judge, 백준 1865번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1865번 웜홀

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1865

1865번: 웜홀

---

2) 풀이 과정

* 시간 복잡도 : O(EV)

 

N개의 지점과, M개의 도로, W개의 웜홀이 있는 월드나라의 한 지점에서 출발하여 다시 출발 지점으로 돌아왔을 때, 시간이 되돌아가 있는 경우가 있는지 확인하는 문제입니다.

단, 도로는 방향이 없지만, 웜홀은 방향이 있으며 도착 시간이 뒤로 갑니다.

 

저의 경우, 벨만 포드 알고리즘을 적용하였고, Python을 사용했습니다.

우선, 주어지는 정보를 방향을 고려하여 인접 리스트로 구현한 뒤, 벨만 포드 알고리즘을 적용하여 문제를 해결했습니다.

헷갈렸던 부분은 시작점이 1번 지점이 아닐 수도 있다는 점이었는데, 임의의 한 지점에서 출발을 하므로 단순히 그래프상에 음의 사이클이 있는지 없는지 확인만 하면 되는 문제로 귀결됩니다.

따라서, 최단 경로를 기록할 리스트의 1번 인덱스에 0으로 초기화할 필요가 없으며, 벨만 포드 알고리즘에서 현재 노드의 값이 INF(무한대)인지 아닌지 확인하는 조건을 넣으면 안 됩니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
 
def bellmanFord():
    global isPossible
 
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            for wei, vec in adjList[j]:
                if dist[vec] > wei + dist[j]:
                    dist[vec] = wei + dist[j]
                    if i == N:
                        isPossible = False
                    
 
T = int(input())
 
for _ in range(T):
    N, M, W = map(int, input().split())
 
    INF = 2147483647
    dist = [INF for _ in range(N + 1)]
 
    adjList = [[] for _ in range(N + 1)]
 
    for _ in range(M):
        S, E, T = map(int, input().split())
 
        adjList[S].append((T, E))
        adjList[E].append((T, S))
    
    for _ in range(W):
        S, E, T = map(int, input().split())
 
        adjList[S].append((-T, E))
    
    isPossible = True
    
    bellmanFord()
 
    print("NO" if isPossible else "YES")

---