[백준] 1865 웜홀

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

노드간 가중치에 음수가 포함이 되어 다익스트라로는 해결이 어렵다고 생각하여 이전에 학습한 '벨만-포드' 알고리즘을 적용했습니다.

 

어떠한 지점에서 출발하여 다시 그 지점으로 돌아왔을때 시간이 줄어드는 경우를 찾아야 하는데, 만약에 한번 확인을 하여 계속 해서 값이 줄어드는 싸이클이 존재하는지 여부만 찾으면 된다고 생각했습니다.

2) 알고리즘

• 벨만-포드

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')


def solution():
    distance[1] = 0                                         # 출발 도시 거리는 0으로 초기화

    for i in range(1, N+1):                                 # 도시의 개수만큼 반복하여 확인
        for j in range(1, N+1):                             # 도로 및 웜홀의 개수만큼 반복
            for e in linked[j]:
                if distance[e[1]] > distance[j] + e[0]:     # 새로운 거리값이 더 짧은 거리값이라면 갱신
                    distance[e[1]] = distance[j] + e[0]

                    if i == N:                              # 도시의 개수만큼 반복하였는데, 계속 값이 바뀐다면
                        return True                         # 음의 무한 싸이클 존재
    return False


TC = int(sys.stdin.readline())                              # 테스트케이스 개수

for _ in range(TC):
    N, M, W = map(int, sys.stdin.readline().split())        # 도시의 개수, 경로의 개수, 웜홀 개수
    distance = [1e10] * (N+1)                               # 각 도시로 가는데 소요되는 거리(시간)
    linked = [[] for _ in range(N+1)]                       # 각 도시 연결 관계

    for _ in range(M):                                      # 도로
        S, E, T = map(int, sys.stdin.readline().split())    # 출발 도시, 도착 도시, 도시 소요 시간
        linked[S].append((T, E))                            # 도시 연결 관계 추가
        linked[E].append((T, S))

    for _ in range(W):                                      # 웜홀
        S, E, T = map(int, sys.stdin.readline().split())    # 출발 도시, 도착 도시, 돌아가는 시간
        linked[S].append((-T, E))
    
    if solution():          # 음수로 인해 무한 싸이클 발생하는 곳이 있다면, YES 출력
        print('YES')
    else:
        print('NO')

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

어떠한 지점에서 출발하고 돌아온다고 생각하여 모든 노드를 탐색하려고하여 어려움이 있었습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

1865번: 웜홀

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다