[백준 1219] 벨만-포드 알고리즘 - 파이썬 Python

오민식의 고민

문제

오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.

오민식은 고민에 빠졌다.

어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.

오민식은 도착 도시에 도착할 때, 가지고 있는 돈의 액수를 최대로 하려고 한다. 이 최댓값을 구하는 프로그램을 작성하시오.

오민식이 버는 돈보다 쓰는 돈이 많다면, 도착 도시에 도착할 때 가지고 있는 돈의 액수가 음수가 될 수도 있다. 또, 같은 도시를 여러 번 방문할 수 있으며, 그 도시를 방문할 때마다 돈을 벌게 된다. 모든 교통 수단은 입력으로 주어진 방향으로만 이용할 수 있으며, 여러 번 이용할 수도 있다.

입력

첫째 줄에 도시의 수 N과 시작 도시, 도착 도시 그리고 교통 수단의 개수 M이 주어진다. 둘째 줄부터 M개의 줄에는 교통 수단의 정보가 주어진다. 교통 수단의 정보는 “시작 끝 가격”과 같은 형식이다. 마지막 줄에는 오민식이 각 도시에서 벌 수 있는 돈의 최댓값이 0번 도시부터 차례대로 주어진다.

N과 M은 50보다 작거나 같고, 돈의 최댓값과 교통 수단의 가격은 1,000,000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착했을 때 돈을 무한히 많이 가지고 있을 수 있다면 "Gee"를 출력한다.

예제 입력 

5 0 4 7
0 1 13
1 2 17
2 4 20
0 3 22
1 3 4747
2 0 10
3 4 10
0 0 0 0 0

예제 출력 

-32

---

벨만 포드 알고리즘

많이 알려져있는 다익스트라가 (시간 복잡도 O(ElogV)) 최단거리 구하는 알고리즘이라면, 벨만-포드 알고리즘(시간 복잡도 O(VE))은 다익스트라 보단 조금 느리지만, 음수엣지가 있어도 수행할수 있는 알고리즘입니다.

 

음수 엣지가 있는 그래프 탐색에선 '음수 사이클'이 생기는데, 그 음수 사이클을 판별하는 용도로도 쓸수 있습니다.

 

음수 사이클 같은 경우는 위 그래프의 2,4,5 노드의 사이클이라고 보시면 됩니다.

한 바퀴 돌때마다 -1씩 감소하므로, 최단거리가 음의 무한대로 발산할 수 있기 때문에 이 경우는 최단거리가 없는 경우입니다.

음의 엣지가 있는 그래프에서는 최단 거리를 구할 땐 음수 사이클이 없는지 확인하고 출력해야합니다

---

1. 등록된 모든 엣지를 가지고 엣지리스트와 각 노드별로 거리 리스트를 만듭니다

 

거리 리스트 (출발점이 1이라고 할때) INF는 무한대를 의미합니다

노드	1	2	3	4	5
최단 거리	0	INF	INF	INF	INF

 

엣지 리스트 (벨만-포트 법은 다익스트라와 다르게 엣지 중심으로 탐색합니다.)

엣지	1	2	3	4	5	6
시작	1	2	1	3	4	5
끝	2	5	3	4	2	5
가중치	8	5	3	7	-4	2

---

2.모든 엣지를 전부 한번씩 탐색해서 거리리스트를 업데이트 합니다.

dist가 거리리스트라고 할때,

dist[시작] + 가중치 <  dist[끝] 를 만족하면 dist[끝] = dist[시작] + 가중치로 업데이트 합니다

dist[시작]의 값이 INF이면 아직 도달하지 못한 노드이므로 수행하지 않습니다.

나중에 이 방식을 N-1 반복하면 완전히 다 탐색하게 되어있습니다.

---

3. 노드의 갯수가 N일때, 2번의 방법을 N-1회 반복합니다. 최단거리를 구할수 있는 최소한의 반복입니다.

 

4. 또 한번 2번의 방법을 다시 수행하고, 거리리스트가 업데이트 되면 음수 사이클이 있다고 판별할 수 있습니다. 한번도 업데이트가 안되면 음수사이클이 없으므로 최댓값 그대로 출력하면 됩니다.

---

문제 풀이

 

핵심 아이디어

최단거리를 구하는 문제가 아니라 최다로 돈을 버는게 목적입니다. 그러므로 거리리스트가 아닌, 받을 수 있는 최대 돈 리스트인 result를 만들었습니다.

그래서 엣지마다 비용을 빼야되고 특정 노드를 도착하면 돈을 얻습니다.

노드는 엣지를 통해 도착하는 것이므로 엣지의 시작, 끝, 가중치가 있을때, 특정 노드가 '끝'에 포함된다면 그만큼 돈을 얻는다고 볼 수 있습니다.

1번 노드까지 갈때 얻을 수 있는 돈이 5고, 1->2 로 가는 엣지의 비용이 5고, 2번 노드를 도착할때 10의 돈을 번다고 가정하겠습니다.

그럼 그 엣지를 이용하면 총 10(보상)-5(비용) = 5의 순이익이 발생하게 되고, 결국 2번 노드로 가는 최다 금액은 5(1번노드)+5(2번으로 갈때 순이익) = 10이 되는 것 입니다.

그래서 가중치를 w(순이익) = cost(도착지에서 버는 금액) - w(교통비) 로 전부 새로고침하고 벨만-포드 법을 수행합니다.

---

예외처리

벨만-포드법대로 코드를 작성하고 양수사이클이(최다 금액을 구하는 것이므로) 나오면 Gee를 출력할 것입니다(버는 돈이 무한이 되므로) 그러나 양수 사이클이 나와도 모든 도시의 최다 금액을 출력하는것이 아니라 "도착 도시"만의 최다 금액을 출력하는 것이므로 양수사이클이 나와도 Gee를 출력하지 않고 최다 금액을 출력해야하는 경우의 수가 생깁니다.

 

출발도시 1, 도착도시 4 일때, 양수 사이클이 생긴 경우

위에 그래프 같은 경우 양수 사이클이 생겨서, 2,3의 최대 금액이 무한대가 됐지만, 어차피 4로 도달을 못하기 때문에 답에 영향을 주기 못하므로, 맹목적으로 Gee를 출력하지 말고, 20원을 출력해야 합니다.

 

N번째 탐색할때, 리스트의 새로 고침이 일어났을때, 바로 양수 사이클있다고 하지 않고, 그 노드를 BFS/DFS 탐색을 이용해서 도착노드가 그 사이클에 포함되어 있는지 검사하고, 포함돼있지 않으면 넘어가고, 포함돼있으면 도착노드도 무한대 금액으로 될것이 뻔하기 때문에 Gee를 출력하면 됩니다.

---

파이썬 코드

dist는 distance의 약자로 거리리스트입니다.

INF는 sys.maxsize를 이용해서 구현할 수 있습니다.

n-1번 반복할때 최단거리가 나오는 것이고, n번째 반복때 만약에 거리리스트가 업데이트 되었다면, BFS탐색을 수행하고, 도착노드에 유무에 따라 isCycle의 값을 True로 만듭니다.

import sys
from collections import deque
input = sys.stdin.readline

fees = []
n,start,end, d = map(int, input().split())
for i in range(d):
    s,e,w = map(int, input().split())
    fees.append((s,e,w))
costs = list(map(int, input().split()))
edges = []
result = [-1 * sys.maxsize] * n
result[start] = costs[start]

for i in fees:
    s,e,w = i
    w = costs[e] - w
    edges.append((s,e,w))

for _ in range(n-1):
    for i in edges:
        s,e,w = i
        if result[s] != -1*sys.maxsize and result[e] < result[s] + w:
            result[e]=result[s] + w


def bfs(start, end):
    q = deque()
    q.append(start)
    visited = [False]*(n)
    visited[start] = True
    while q:
        now = q.popleft()
        # 현재 탐색하는 노드가 도착노드면
        # 양수사이클이 도착노드도 포함한다는 의미
        if now == end:
            return True
        for s,e,w in edges:
            if s==now:
                if not visited[e]:
                    visited[e] = True
                    q.append(e)
    
    return False


isCycle = False
for i in edges:
        s,e,w = i
        if result[s] != -1 * sys.maxsize and result[e] < result[s] + w:
            if bfs(s,end):
                isCycle = True
                break

if result[end] == -1 * sys.maxsize:
    print("gg")
else:
    if isCycle:
        print("Gee")
    else:
        print(result[end])