[백준] 1219번: 오민식의 고민 - 파이썬 (벨만 포드, BFS)

🔈 문제

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

오민식은 고민에 빠졌다.어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.

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

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

 

📝입력

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

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

 

📑출력

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

 

📚 문제 풀이

A에서 B로 가는 교통비보다 B에 방문했을 시에 얻는 돈이 더 많고 이 둘 사이에 사이클이 생길 수 있다면 돈을 무한히 많이 가지고 있을 수 있으니 Gee를 출력하고, 도착할 수 있는 경로가 없다면 gg를 출력하고 나머지 경우에는 가지고 있는 돈의 액수의 최댓값을 출력하면 되었다.

 

사이클의 존재의 여부를 파악할 수 있는 알고리즘은 바로 벨만 포드 알고리즘이다. 벨만 포드 알고리즘으로 문제를 푼 소스코드는 다음과 같다.

 

💻 코드_1

import sys
input = sys.stdin.readline
INF = -int(1e9) # 음의 무한
def bellman(start,end):
    dist = [INF for _ in range(n)] # 초기배열
    dist[start] = money[start] # 가만히 있는경우를 위해 0이 아닌 money[start]로 초기화
    
    for i in range(n-1):
        for u,v,w in city: # 한바퀴 돌아서 갱신
            if dist[u] != INF and dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
    
    if dist[end] == INF: # 도착불가능 gg
        return 'gg'
    
    # 한번 더 돌았을 때 사이클이 생긴다면 Gee
    for u,v,w in city:
        if dist[u] != INF and dist[u] + w > dist[v]:
            if money[end] != dist[end]:
                return 'Gee'
 
    # 최대머니 리턴        
    return dist[end]
n,start,end,m = map(int,input().split()) # 노드개수, 시작, 끝, 간선개수
city = []
for _ in range(m):
    a,b,c = map(int,input().split()) # 시작, 끝, 교통비
    city.append([a,b,-c]) # 교통비는 음수로
money = list(map(int,input().split())) # 방문시 얻는 돈 입력받음
for i in range(m):
    city[i][2] = city[i][2]+money[city[i][1]] # 교통비+방문시 얻는 돈
print(bellman(start,end))

 

무한 값을 음의 무한으로 하였고, A로 가는 교통비에 A 방문시 얻는 비용을 더해준 뒤 벨만 포드를 수행하였다.

그러나 아래의 코드는 틀렸습니다 판정이 나왔다. 이유는 사이클이 생겼을 때인데, 사이클이 생겨도 그 사이클에서 도착지점에 갈 수 없는 경우를 체크해주지 못한채 그냥 사이클이 생기면 Gee를 리턴해주었다.

즉 C와 D에서 뺑뺑이 돌려서 돈을 무수히 많이 만들어도 C나 D에서 도착지점까지 갈 수 없다면 소용히 없는 것이다.

 

예외 케이스
4 0 3 4
0 1 0
1 2 0
2 1 0
0 3 10
10 10 10 10

 

그림으로 보면 조금 더 이해하기 쉽다.

1번과 2번의 사이클이 생겼지만 1번이나 2번에서 도착지점인 3번에 갈 수 없기 때문에 단순히 사이클 체크 후에 Gee를 출력할게 아니라 그 사이클에서 도착지점에 갈 수 있는지 여부를 확인해봐야 하였다. 이 부분은 추가로 BFS를 사용하여 구현하였다.

 

💻 코드_2

from collections import deque
import sys
input = sys.stdin.readline
INF = -int(1e9) # 음의 ㅜ한
def bellman(start,end):
    dist = [INF for _ in range(n)] # 초기배열
    dist[start] = money[start] # 가만히 있는경우를 위해 0이 아닌 money[start]로 초기화
    
    for i in range(n-1):
        for u,v,w in city: # 한바퀴 돌아서 갱신
            if dist[u] != INF and dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
    
    if dist[end] == INF: # 도착불가능 gg
        return 'gg'
    
    # print(city, dist)
    # 한번 더 돌았을 때 사이클이 생긴다면 Gee
    for u,v,w in city:
        # print(dist[u], w, dist[v])
        if dist[u] != INF and dist[u] + w > dist[v]:
            if bfs(v,end):
                return 'Gee'
            else:
                pass
 
    # 최대머니 리턴        
    return dist[end]
 
 
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 a,b,c in city:
            if a==now:
                if not visited[b]:
                    visited[b] = True
                    q.append(b)
    
    return False
 
 
n,start,end,m = map(int,input().split()) # 노드개수, 시작, 끝, 간선개수
city = []
for _ in range(m):
    a,b,c = map(int,input().split()) # 시작, 끝, 교통비
    city.append([a,b,-c]) # 교통비는 음수로
money = list(map(int,input().split())) # 방문시 얻는 돈 입력받음
for i in range(m):
    city[i][2] = city[i][2]+money[city[i][1]] # 교통비+방문시 얻는 돈
 
print(bellman(start,end))

 

🍭 시행착오

🔗 문제링크 오민식의 고민

1219번: 오민식의 고민