[BOJ] 백준 11657 타임머신 (파이썬 python)

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

11657번: 타임머신

 

• 음수 간선이 있을 수 있으므로 벨만포드 알고리즘을 사용해야한다.
• 출력 부분에서 "시간을 무한히 오래 전으로 되돌릴 수 있다면" = 음수사이클이 있다면

 

 

Step1 문제 분석하기

시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 것이다.

이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포드 알고리즘을 사용하면 된다.

 

1. 에지 리스트에 에지 데이터를 저장한 후 거리 리스트를 다음과 같이 초기화한다.

최초 시작점에 해당하는 거리 리스트값은 0으로 초기화한다.

 

 

2. 다음 순서에 따라 벨만-포드 알고리즘을 수행한다.

 

● 벨만-포드 알고리즘 수행 과정

 

① 모든 에지와 관련된 정보를 가져온 후 다음 조건에 따라 거리 리스트의 값을 업데이트한다.

- 출발 노드가 방문한 적이 없는 노드(출발 노드 == INF)일 떄 값을 업데이트하지 않는다.

- 출발 노드의 거리 리스트값 + 에지 가중치 < 종료 노드의 거리 리스트값일 때 종료 노드의 거리 리스트값을 업데이트한다.

 

② '노드 개수 - 1'만큼 ①을 반복한다.

 

③ 음수 사이클 유무를 알기 위해 모든 에지에 관해 다시 한번 ①을 수행한다.

이때 한번이라도 값이 업데이트되면 음수 사이클이 존재한다고 판단한다.

 

 

3. 음수 사이클이 존재하면 -1, 존재하지 않으면 거리 리스트의 값을 출력한다.

단, 거리 리스트의 값이 INF일 경우 -1을 출력한다.

 

 

Step 2 수도 코드

N(노드 개수), M(에지 개수)
edges(에지 정보 저장 리스트)
distance(거리 리스트) #충분히 큰 수로 초기화

for 에지 개수만큼 반복:
	에지 리스트에 에지 정보 저장
    
# 벨만 포드 수행
거리 리스트에 출발 노드 0으로 초기화

for 노드 개수 - 1 만큼 반복:
	for 에지 개수만큼 반복:
    	현재 에지 데이터 가져오기
        if 출발 노드가 무한대가 아니고 종료 노드값 < 출발 노드값 + 에지 가중치:
        	업데이트 수행 -> 종료 노드값 = 출발 노드값 + 에지 가중치

for 에지 개수만큼 반복: # 음수 사이클 존재 여부 확인
	현재 에지 데이터 가져오기
    if 출발 노드가 무한대가 아니고 종료 노드값 < 출발 노드값 + 에지 가중치:
    	업데이트 가능 -> 음수 사이클 존재
        
 
 음수 사이클 미존재 -> 거리 리스트 출력하기 # 단, 거리 리스트의 값이 무한대일 때 -1 출력
 음수 사이클 존재 -> -1 출력

 

Step 3 코드

# 백준 11657 타임머신

import sys
input = sys.stdin.readline
N, M = map(int,input().split())
edges = []
distance = [sys.maxsize] * (N+1)

# 에지 데이터 저장

for i in range(M):
  start,end,time = map(int,input().split())
  edges.append((start,end,time))

distance[1] = 0

for _ in range(N-1): # 최단 거리 구하기
  for start,end,time in edges:
    if distance[start]!= sys.maxsize and distance[end] > distance[start] + time :
      distance[end] = distance[start] + time

mCycle = False

for start,end,time in edges:
  if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
    mCycle = True

if not mCycle:
  for i in range(2,N+1):
    if distance[i] != sys.maxsize:
      print(distance[i])
    else: 
      print(-1)


else:
  print(-1)

 

• 참고자료 인프런 강의

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148458 

학습 페이지