[백준] 오민식의 고민 : 벨만-포드

문제

1219 : 오민식의 고민

아이디어

노드(도시)간 이동에 드는 지출이 있고 노드에 도달했을 때 벌 수 있는 수입이 있다.

기본적인 아이디어는 가장 적은 가중치의 경로로 이동하면서 가장 많은 수입을 주는 노드를 거쳐서 도착점에 도착하는 것이다.

출력의 종류는 gg, Gee, 정수 3가지가 있는데, 문제에서 Gee를 출력하는 조건이 무한히 많은 돈을 벌 수 있을 때 이다.

나는 이 조건을 보고 최단 거리 경로에서 무한한 값을 가지는 경우를 판단하는 알고리즘을 쓸 수 있을 것이라고 판단했다.

벨만-포드

벨만-포드 알고리즘은 다익스트라 알고리즘과 동일한 결과를 구해준다.

1:N의 최단거리, 즉 시작 노드에서 다른 각각의 노드까지 도달 할 때의 최단 거리를 구할 수 있는 알고리즘이다.

다익스트라 알고리즘과의 차이점

음수 사이클이 존재하는 그래프에서 벨만-포드 알고리즘을 사용할 수 있고 그렇지 않은 그래프에서는 다익스트라 알고리즘을 사용한다.

라는걸 이미 알고 있지만 이런 식으로 알고리즘을 외우는 것은 좋지 않다.

각각의 알고리즘이 어떤 문제상황에서 쓰이는 지에 대해서 외우는 것보다 정확한 매커니즘을 파악하고 "이래서 이럴때 사용하는 구나" 라고 이해하는 편이 좋다.

벨만-포드 알고리즘은 모든 간선을 $V-1$번씩 탐색한다.

왜?

많은 블로그에서 이 부분을 설명해주지 않는다. 설령 설명하더라도 명료하지 못한 경우가 대다수다.

내 설명도 완벽하다고는 할 수 없지만 최대한 벨만-포드 알고리즘을 모르는 사람에게 설명해주듯이 설명해보겠다.

시간복잡도

알고리즘은 항상 경계조건을 주의해야한다.
대부분의 오류는 최소경계, 최대경계에서 발생한다.

벨만-포드 알고리즘의 시간복잡도를 이해하기 위해서 최대경계 조건을 생각해보자.

먼저 '최단거리' 라는 것의 최악의 상황을 고려해보자.
그래프가 1-2-3-4-5-6-7 과 같이 일직선으로 연결 되어 있으면 1번부터 7번까지 가는 최단경로는 어쩔 수 없이 자기 자신을 제외한 모든 노드를 다 거치는 경로이다.

자기 자신을 제외한 모든 노드의 개수(#)를 생각해보면 전체 노드의 개수 $V$에서 자기자신 $1$을 뺀 $V-1$개의 노드이다.

모든 간선을 탐색해서 최단 거리를 구하고자 하는 알고리즘이 있다고 생각하자.
이 알고리즘은 최단 거리를 구하기 위해 모든 간선을 일일이 탐색해서 최단 거리를 구하려고 한다. 이 알고리즘을 사용해서 위의 예제 상황의 정답을 구하려면 최소 몇번 탐색해야 할까?

물론 간선을 1-2, 2-3, 3-4, 4-5, 5-6, 6-7 의 순서대로 탐색할 수 있다는 보장이 있으면 모든 간선을 딱 한 번 탐색해서 정답을 구할 수 있다.

하지만 문제에서 특별한 조건이 없는 이상 이런게 보장될 리가 없다.

그래서 우리는 최악의 경우 최단 거리 자체가 $V-1$개의 간선(=자기 자신을 제외한 $V-1$개의 노드)을 거친다는 것을 알고 있기 때문에 적어도 $V-1$번 반복해야 한다는 것을 알 수 있다.

방금 전에 말한 모든 간선을 탐색해서 최단 거리를 구하고자 하는 알고리즘이 바로 벨만-포드 알고리즘이다.

우리는 이제 $V-1$의 이유를 완벽히 수학적으로는 아니어도 어느 정도 "아 이래서 $V-1$번 이라는 iteration이 필요하구나" 라는 걸 개념적으로 이해할 수 있게 되었다.

따라서 벨만-포드 알고리즘의 시간복잡도는 $O((V-1)E) == O(VE)$ 이다.

음수 사이클

벨만-포드 알고리즘에서는 음의 가중치 간선이 존재할 수 있기 때문에 이 간선으로 인해 무한히 작은 경로를 만들어 낼 수 있다.

1->2->3 경로를 통해서 0->4로 가는 도중 무한히 작은 경로를 만들어 낼 수 있다.

그렇기 때문에 딱 한번만 더 모든 간선을 탐색해서 최단 경로가 갱신되는지 갱신되지 않는지를 판단한다.

어떤 노드 N의 출발 노드로부터의 최단경로가 갱신된다면 그 노드에서 음수 사이클이 발생한다고 생각할 수 있다.

1219 : 오민식의 고민 이 문제에서는 음수 사이클을 판단하고 음수 사이클을 생성하는 노드가 도착점에 영향을 주는지 확인 해야 한다.

풀이

벨만포드 알고리즘을 사용하되 음수사이클이 발생하는 노드에서 도착점을 갈 수 있는지 없는지에 대해 판단해줘야 한다.
어떤 노드에서 음수사이클이 발생해도 도착점과 무관한 노드라면 정답을 낼 수 있다.

음수사이클이 발생하는 노드에서 BFS나 DFS를 수행해서 도착점까지 갈 수 있는지 없는지에 대해서 판별할 수 있다.

코드

import sys
from collections import deque

In = lambda:sys.stdin.readline().rstrip()
MIS = lambda:map(int,In().split())


def b_f(start,st_earn,end,N):
	INF = float("inf")
	dist = [ INF ]*N
	dist[ start ] = -st_earn
	for n in range(N-1):
		for i in range(N):
			if dist[ i ]==INF: continue
			for p,d in grp[ i ]:
				if dist[ p ] > d+dist[ i ]-earn[ p ]:
					dist[ p ] = d+dist[ i ]-earn[ p ]

	# 음의 cycle 체크 : v번째 loop를 통해서 값의 변화가 있는지 없는지 판단.
	for i in range(N):
		for p,d in grp[ i ]:
			if dist[ p ] > d+dist[ i ]-earn[ p ]:
				if findRoute(i,p,end):  # 값의 변화가 존재하는 노드에서 도착점으로 갈 수 있는지 판단.
					return False,dist
	return True,dist


def findRoute(i,p,end):
	dq = deque([ i,p ])
	vist = [ 0 ]*N
	while dq:
		cur = dq.popleft()
		if vist[ cur ]==1: continue
		if cur==end: return True
		vist[ cur ] = 1
		for nxt,d in grp[ cur ]:
			if vist[ nxt ]==1: continue
			dq.append(nxt)
	return False


def init():
	N,start,end,M = MIS()
	grp = [ [ ] for i in range(N) ]
	for m in range(M):
		s,e,d = MIS()
		grp[ s ].append((e,d))
	earn = [ *MIS() ]
	return N,grp,earn,start,end


N,grp,earn,start,end = init()
flg,dist = b_f(start,earn[ start ],end,N)
if flg==False:
	print("Gee")
else:
	print(-dist[ end ] if dist[ end ]!=float("inf") else "gg")

# 4 0 3 4
# 0 1 0
# 1 2 0
# 2 1 0
# 0 3 10
# 10 10 10 10
# output = 10


# 4 1 3 4
# 0 1 0
# 1 2 0
# 2 1 0
# 0 3 10
# 10 10 10 10
# output = gg

# 3 0 2 4
# 0 1 9999
# 1 2 9999
# 1 1 9999
# 0 2 0
# 10000 10000 10000
# output = Gee

# 5 0 4 6
# 0 1 10000
# 1 2 0
# 2 1 0
# 1 3 0
# 0 3 0
# 3 4 0
# 0 0 1 0 0
# output = Gee