[파이썬] 1219 오민식의 고민 (백준)

1. 문제 설명

문제 : 1219 - 오민식의 고민 https://www.acmicpc.net/problem/1219

사용 언어 : 파이썬 (Pypy3)

 

문제요약 :

각 거리마다 잃는 돈과 얻는 돈이 주어질 때, 최대로 갖게 될 수 있는 돈을 구하라. 이때, 도착을 못하는 경우나 돈을 무한히 많이 가질 수 있는 경우라면 각각 gg와 Gee를 출력하라.

 

(이 문제를 풀면서 오민식보다 더 심한 고민에 빠졌었다.)

---

2. 문제 풀이

해설 : 

일반적인 벨만포드를 사용한다. 이때,  사이클이 존재하는지를 알기 위해 bfs를 사용하였다.

또한 얻을 수 있는 돈과 잃어야 하는 돈이 각각 주어짐으로 해당 구간에서 얻을 수 있는  돈을 미리 구해두었다.

 

코드 :

import sys; input = sys.stdin.readline
from collections import deque
INF = sys.maxsize

def BellmanFord(start):
    distance[start] = earn_max[start]

    for i in range(N-1):
        for j in range(M):
            now_node, next_node, cost = road[j][0], road[j][1], road[j][2]

            if distance[now_node] != -INF and distance[next_node] < distance[now_node]+cost:
                distance[next_node] = distance[now_node]+cost
    return

def bfs(start, end):
    q = deque([start])
    visited = [False for i in range(N)]
    visited[start] = True

    while q:
        n = q.popleft()
        if n == end: return True

        for i in range(M):
            now_node, next_node = road[i][0], road[i][1]
            if now_node == n and (not visited[next_node]):
                visited[next_node] = True
                q.append(next_node)

    return False

N, A, B, M = map(int,input().split())

distance = [-INF for i in range(N)]

temp = [list(map(int,input().rstrip().split())) for i in range(M)]
earn_max = list(map(int,input().rstrip().split()))

# 미리 얻을 수 있는 돈 구해두기
road = []
for i in range(M):
    road.append([temp[i][0], temp[i][1], earn_max[temp[i][1]]-temp[i][2]])

BellmanFord(A)

if distance[B] == -INF: print('gg')

else:
    for i in range(M):
        now_node, next_node, cost = road[i][0], road[i][1], road[i][2]
		
        if distance[now_node] != -INF and distance[next_node] < distance[now_node]+cost:
        	# 사이클 있는지 확인
            if bfs(next_node, B): print('Gee'); exit()
    print(distance[B])

---

앞으로 코딩과 알고리즘 관련 글을 업로드할 예정입니다!

아직 배우는 중이라서 부족한 점이 있으면 댓글 남겨주시면 감사하겠습니다!!