[백준] 1219번: 오민식의 고민

문제

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

풀이

벨만포드 알고리즘과 BFS를 활용한 풀이

import sys
from collections import deque

INF = sys.maxsize

# 입력을 받아서 처리합니다.
N, start_city, end_city, M = map(int, input().rstrip().split(" "))

# 그래프를 생성하고 초기화합니다.
graph = []
for _ in range(M):
    start, end, weight = map(int, input().rstrip().split(" "))
    graph.append([start, end, -weight])  # 이동하는데 드는 비용을 음수로 저장합니다.

# 각 도시에서 벌 수 있는 돈을 입력 받습니다.
cities_weight = list(map(int, input().rstrip().split(" ")))

def solution(N, start_city, end_city, M, graph, cities_weight):
    # 벨만-포드 알고리즘을 이용합니다.
    for i in range(M):
        # 그래프에 저장된 이동 비용에 해당 도시에서 벌 수 있는 돈을 더합니다.
        graph[i][2] += cities_weight[graph[i][1]]

    # 각 도시에 도착했을 때 가지고 있을 수 있는 돈의 최대값을 저장하는 리스트입니다.
    money = [-INF] * N
    # 시작 도시에서는 해당 도시에서 벌 수 있는 돈을 가질 수 있습니다.
    money[start_city] = cities_weight[start_city]
    for _ in range(N):
        for mid, end, weight in graph:
            # 시작 도시에서 현재 도시까지 가지고 있을 수 있는 돈이 있고, 그 돈과 현재 도시에서 벌 수 있는 돈의 합이 
            # 현재 도시에서 가지고 있을 수 있는 돈의 최대값보다 큰 경우, 값을 업데이트합니다.
            if money[mid] != -INF and money[end] < money[mid] + weight:
                money[end] = money[mid] + weight
                # 만약 N번째 반복에서도 값이 업데이트 된다면, 그것은 음의 사이클이 존재한다는 의미입니다.
                if _ == N-1:
                    reachable = [False]*N
                    queue = deque([mid])
                    # BFS를 이용해 해당 사이클이 도착 도시에 도달 가능한지 확인합니다.
                    while queue:
                        curr = queue.popleft()
                        if not reachable[curr]:
                            reachable[curr] = True
                            for next_start, next_end, next_weight in graph:
                                if next_start == curr:
                                    queue.append(next_end)
                    # 만약 도착 도시에 도달 가능하다면, 돈을 무한히 벌 수 있다는 의미이므로 "Gee"를 출력합니다.
                    if reachable[end_city]:
                        print("Gee")
                        return

    # 도착 도시에 도달할 수 없는 경우, "gg"를 출력합니다.
    if money[end_city] == -INF:
        print("gg")
    else:  # 도착 도시에 도달할 수 있는 경우, 가지고 있는 돈의 최대값을 출력합니다.
        print(money[end_city])

    return

# solution 함수를 호출하여 문제를 해결합니다.
solution(N, start_city, end_city, M, graph, cities_weight)