[백준/1219] 오민식의 고민 (Python)

Problem : https://www.acmicpc.net/problem/1219

1219번: 오민식의 고민

 

Difficulty : Platinum 5

 

Status : solved

 

Time : 01:24:58

 

---

 

문제 설명

 

 

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

오민식은 고민에 빠졌다.

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

이 나라에는 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

 

 

---

 

풀이

 

오민식 고민보다 내 고민이 더 커졌던 문제... 핵심 알고리즘 찾는것부터 수많은 엣지 케이스 고려까지 하나부터 열까지 속을 썩였다.

수많은 실패의 향연

돈을 무한히 많이 가지고 있다 == 음수 사이클이 존재한다 이므로, 음수 사이클을 판별할 수 있으며 시작점에서 끝점까지의 최단경로를 찾을 수 있는 벨만-포드 알고리즘을 차용하는 것까지는 좋았다. 즉

 

• 벨만 포드 알고리즘을 사용하여 최단거리를 구하고
• 만약 최단거리가 초기값에서 갱신되지 않았다면 "gg"를 출력
• 갱신되었되 음수 사이클이 존재한다면 "Gee"를 출력
• 위 두 경우에 해당하지 않는다면 최대 이윤값(최단거리)를 출력

 

..으로 끝내볼 수 있겠지만, 문제는 최대 이윤값 경로에 사이클이 포함되지 않을 경우이다. 즉 음수 사이클 경로상에서 도착점까지 도달할 수 없다면, 돈을 무한히 가질 수 없으므로 정답을 올바르게 출력해야 한다.

 

즉 사이클을 판별하되, 사이클내 노드에서 도착점까지 도달할수 있는지 여부 역시 검사해야 한다. 나는 dfs로 이를 해결하였다.

 

p.s. 도시 도착 시점에 값이 증가하므로, distance 리스트를 갱신할 때 이를 고려하여 갱신하거나, 아예 엣지 리스트를 처음부터 갱신해주는 방법이 있다(도착점이 j인 모든 값에 대해 이윤값 money[j]를 일괄적으로 더해주기만 하면 된다) 또한 시작점 == 끝점일 때 그 도시 상에서는 이윤을 볼 수 있으므로, distance[start] = money[start]로 초기화해주도록 하자.

 

 

 

풀이 코드

import sys
input = sys.stdin.readline

MAX = float('inf')

N, S, E, M = map(int, input().split())
edge_list = [[-MAX]*N for _ in range(N)]
for _ in range(M) :
  a, b, c = map(int, input().split())
  edge_list[a][b] = max(edge_list[a][b], -c)
money_list = list(map(int, input().split()))
for i in range(N) :
  for j in range(N) :
    edge_list[i][j] += money_list[j]
dist_list = [-MAX]*N
dist_list[S] = money_list[S]

visited = [False]*N
def dfs(x) :
  if x == E :
    return True
  for i in range(N) :
    if edge_list[x][i] > -MAX and not visited[i] :
      visited[i] = True
      tmp = dfs(i)
      visited[i] = False
      if tmp :
        return True
  return False

for _ in range(N) :
  for i in range(N) :
    for j in range(N) :
      if edge_list[j][i] > -MAX and dist_list[i] < dist_list[j] + edge_list[j][i] :
        dist_list[i] = dist_list[j] + edge_list[j][i]
if dist_list[E] == -MAX :
  print("gg")
  exit()
for i in range(N) :
  for j in range(N) :
    if edge_list[j][i] > -MAX and dist_list[i] < dist_list[j] + edge_list[j][i] :
      if dfs(i) :
        print("Gee")
        exit()

print(dist_list[E])

풀이 완료!