[백준] 11657 타임머신

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

노드간 거리를 나타내는 간선의 가중치가 음수가 있는 경우도 있기 때문에, 다익스트라로는 어려울거라 생각했습니다.

간선 가중치에 음수가 들어간 경우 사용하는 벨만-포드 알고리즘을 학습하여 접근했습니다.

2) 알고리즘

• 벨만-포드
  어떠한 노드에서 다른 노드로 이동하는 거리를 구할때 사용 (가중치가 음수가 있는 경우에도 사용 가능)

3) 풀이 코드

사용 언어 - Python

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


def solution(start: int):                                               # 벨만포드 (시작 노드)
    dist[start] = 0                                                     # 시작 위치의 거리는 0으로 세팅
    
    for i in range(1, N+1):                                             # 도시의 개수만큼 반복하여 확인
        for j in range(1, N+1):                                         # 모든 도시들의 버스 경로 확인 (모든 간선 확인)
            for e in linked[j]:
                if dist[j] != 1e10 and dist[e[1]] > dist[j] + e[0]:     # 시작 지점이 무한대가 아니고, 새로운 거리가 더 짧을때
                    dist[e[1]] = dist[j] + e[0]                         # 새로운 거리 갱신

                    if i == N:                                          # N번 확인했을때도 계속 값 갱신이 일어난다면 무한 반복
                        return True
    return False


N, M = map(int, sys.stdin.readline().split())           # 도시 개수, 버스 경로 개수
linked = [[] for _ in range(N+1)]                       # 버스 경로들 저장할 리스트
dist = [0] + [1e10] * N                                 # 어떠한 도시에서 특정 도시들로 향하는 거리

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())    # 버스 경로들 출발지점, 도착지점, 거리
    linked[A].append((C, B))
    

if solution(1):             # 계속 무한히 반복이면 -1 출력
    print(-1)
else:
    for d in dist[2:]:
        if d == 1e10:       # 갈수없는 도시라면 -1 출력
            print(-1)
        else:
            print(d)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

처음에 다익스트라를 사용하여 풀이를 하려 했으나, 무한 순환이 발생하는 경우 해결하기 어려웠습니다.

(1) 참고 사이트

• 블로그
  벨만-포드 개념 및 코드 작성 방법 학습했습니다.

2) 새롭게 학습한 내용

음수 가중치가 있는 경우에, 최소 경로를 구하는 벨만-포드 알고리즘을 학습했습니다.

---

🔗 문제 링크

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

11657번: 타임머신

 

 

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