알고리즘 스터디 9일차

목차

1. 벨만-포드 (Bellman-Ford)

2. [벨만-포드 실전 문제]

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 벨만-포드

그래프에서 최단 거리를 구하는 알고리즘

특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 (=다익스트라)

음수 가중치 에지가 있어도 수행 가능

전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음

시간복잡도 : O(VE)

 

에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화,          출발 노드는 0 나머지 노드는 무한대

 

업데이트 조건과 방법 : D[s] != ∞ (시작노드는 무한대면 안된다.) 이며 D[e] > D[s] + w 일 때 D[e] = D[s] + w 로 리스트의 값을 업데이트 (e : 도착노드인덱스, s : 출발노드인덱스, w : 가중치)

모든 에지를 확인해 정답 리스트 업데이트           업데이트 반복 횟수 : 노드 개수 -1

 

따라서 정답리스트는 [0 8 3 10 13]

 

음수 사이클 확인해야 하는 이유 : 음수 사이클을 도는 것이 최단거리로 나가는것 보다 더 이득(값이 적어짐)이므로 계속 반복 (음수 가중치가 있는 사이클)

음수 사이클 확인 하는 법

위의 그림에서 D[4] = 10이고 D[5] = 11 이고 D[5]에서 D[4]로 가는 가중치는 -2 이므로 11-2는 9 이다.

따라서 위의 정답리스트를 확인하면 9로 업데이트 된것을 확인 할수 있는데 이렇게 업데이트가 일어나면 음수사이클을 돌았다는 얘기가 된다. (최단거리 N-1에지로 업데이트 -> 한번더 업데이트를 시도해서 업데이트가 되면 음수 사이클이 존재한다는 뜻이고 최단거리를 못구함.)

 

2. 벨만-포드 실전문제

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

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  # 시작 노드의 거리를 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

nCycle = False

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

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

 

계속 실패해 해설을 참고해 코드를 작성했다. 알고리즘에 대한 이해도 부족했지만 코드를 짜는 법도 알아두어야겠다. 특히 코딩테스트를 준비하면 주피터로 코드를 작성하기엔 문제 난이도가 높아질 수록 시간초과에서 벗어날 수 없다. 따라서 IDE환경인 Visual Studio로 코드를 작성하기 시작했고 sys모듈 사용법도 틈틈히 공부할 필요가 있다.