[백준 파이썬] 11657 타임머신

📌문제 출처

백준 단계별 문제풀이 : 최단경로
https://www.acmicpc.net/problem/11657

11657번: 타임머신

❓ 문제

 

✍알고리즘 공부

• 최단 경로 문제는 다음과 같이 주어진 상황에 맞는 알고리즘을 사용한다.
  - 다익스트라 : 시작점으로 부터 나머지 정점까지 최단거리를 구할 때
  - 플로이드 워셜 : 각 정점간 최단경로를 모두 구할 때
  - 벨만 포드 : (다익스트라와 같은 경우에서) 음의 가중치가 존재할 때
• 벨만 포드 알고리즘은 음의 순환이 발생하는지를 알려줄 뿐더러
  음의 가중치가 있지만 음의 순환이 없는 경우에는 다익스트라 알고리즘과 동일한 결과를 낸다.
• 최단경로로 갈 수 있는 이웃 노드들을 확인하고 바로 갱신하는 다익스트라와는 다르게
  모든 경로를 노드의 개수만큼 확인해주어야하기에 시간복잡도는 큰 편이다.
• 벨만 포드 알고리즘에서 음의 순환인지 확인하기 위해서 싸이클(모든 간선을 확인하는 과정)을
  n번 돌았을 때 갱신이 되는지 확인한다.

음의 순환이 발생한 순간

• 위와 같은 구조에서 한번 전체 간선을 확인할 때마다 계속 -1씩 갱신 된다. 이처럼 계속 갱신되는 노드가 생긴다면 음의 순환이 있다는 것을 확인할 수 있다.
• 그렇다면 왜 n번(노드 개수 만큼) 확인해야할까?
  그것은 "시작 노드 부터 n번째 노드까지의 최단 경로는 최대 (n-1)개의 간선을 지난다"라는 전제때문이다.
  타임머신 예제들로 확인해보자.

음수 간선은 있지만 음수 순환은 없는 경우

• 위와 같은 상황에서 주어진 간선 순서대로 노드의 최단 경로를 갱신해주면 한번의 싸이클을 돌고 종료된다.

음수 간선이 포함된 음수 순환의 경우

• 음수 순환이 있는 경우에는 n번째 싸이클을 진행해도 계속 갱신이 되고 있다.

최악의 경우 : 음수 순환이 없지만 n-1번째까지 갱신이 되는 경우

• 위의 경우에는 조금은 억지스러운 예제이지만 (n-1)번째까지 갱신이 되고 n번째부터는 갱신이 되지 않는다.
  위처럼 최단 경로로 가는 최대의 간선수는 n-1이고 갱신이 한 싸이클마다 한 노드씩 갱신된다면 최대 n-1번 싸이클까지는 갱신이 된다.
• 이때문에 n번째 싸이클까지 확인했을 때 갱신이 되지않을 경우 음수 순환이 아니라고 판단할 수가 있다.

📗 문제 풀이

• 수도 코드(의사 코드)

음의 간선이 존재해 음수 순환이 발생할 수 있으므로 다익스트라가 아닌 벨만 포드 알고리즘 사용
- 입력
    n(노드 개수), m(간선 개수)
    lines = [[출발 노드, 도착 노드, 이동 시간]] # 간선 정보
1. 변수 생성
    short_cut = 노드의 인덱스마다 최단 경로를 담은 리스트(초기는 무한대)
2. 벨만 포드 알고리즘 함수 생성
    출발 노드 최단 경로 0으로 초기화
    for i in range(n) : n번 확인
        for j in range(m) : 모든 간선을 확인하면서 최단 경로 갱신
            출발 노드, 도착 노드, 이동 시간 = j번째 간선 정보
            if 출발 노드의 현재 최단 경로가 무한대가 아니고(무한대면 덧셈 불가)
                and 도착 노드 현최경 > 출발 노드 현최경 + 이동 시간 :
                short_cut의 도착 노드 현최경 갱신
                if i == n-1 : n번째 확인했는데도 갱신이 된거면
                    return False 음수 순환 발생
    return True 음수 순환 미발생
3. 정답 출력
    if 벨만 포드가 음수 순환이다 : -1 출력
    else 음수 순환이 아니다 :
        short_cut 2번 노드부터 출력(1번 노드가 시작점이므로), 무한대면 -1 출력

• 풀이 코드

input = open(0).readline

def bmf():
    short_cut[1] = 0 # 출발 노드 초기화
    for i in range(n) : # n번 확인
        for sta,end,dist in lines : # 모든 간선 확인
            if short_cut[sta] != inf and short_cut[end] > short_cut[sta]+dist :
                short_cut[end] = short_cut[sta]+dist
                if i == n-1 : # n번째 확인했는데도 갱신이 된거면
                    return False # 음수 순환 발생
    return True # 음수 순환 미발생

def solution():
    if not bmf() : # 음수 순환이라면
        print(-1)
    else :
        for i in range(2,n+1):
            print(short_cut[i] if short_cut[i] != inf else -1)
    return

if __name__ == '__main__':
    n,m = map(int,input().split()) # 노드 개수, 간선 개수
    lines = [list(map(int,input().split())) for _ in range(m)] # 간선 정보
    inf = float('inf')
    short_cut = [inf]*(n+1) # 노드 인덱스에 맞춘 최단 시간 리스트
    solution()