[백준 1219] 오민식의 고민

문제 출처 : https://www.acmicpc.net/problem/1219

1219번: 오민식의 고민

 

관련 문제 확인

이 문제는 골목길 문제의 확장판이라고 할 수 있습니다. 골목길에 대한 해설은 아래 링크를 타고 들어가면 확인해 볼 수 있습니다.

https://wikidocs.net/225235

03. 골목길[백준 1738]

 

골목길 문제는 최소 경로를 구하는 것이 아니라 최대 경로를 구하는 문제 입니다. 그러다보니 음의 사이클이 아닌 양의 사이클을 찾아야 합니다. 그리고 양의 사이클이 있는 경우 무조건 -1을 출력하는 것이 아니라 경로상 문제가 있는지 확인해야 한다고 하였습니다.

이 문제에서 생각할 점

이 문제는 골목길에서 한발 더 나아가 도착시 최대 금액을 출력해야 합니다. 최대가 되는 경우 무한대가 될 수도 있다는 것을 주의 해야 합니다. 즉 이렇게 3가지 경우에 대해 고민해야 합니다.

1. 도착이 불가능한 경우(gg)
2. 도착해보니 돈이 무한대인 경우(Gee)
3. 도착했을 때 가진 금액

1번과 3번은 이전 다른 벨만포드 문제와 같기 때문에 고민할 필요가 없습니다. 하지만 2번은 조금 고민이 필요합니다. 왜냐하면 이 문제는 음의 사이클이 있는지 확인하는 것이 아니라 도착지에 도착했을 때 돈이 무한대인지 아닌지 확인해야 하기 때문입니다. 즉 음의 사이클의 영향이 도착지에 전파 되었는지를 확인해야 합니다.

 

 이런 케이스를 생각해 보겠습니다. 0번부터 2번까지 사이클이 있는지 확인해야 합니다. 벨만 포드 알고리즘 특성상 N - 1 번째 반복까지는 거리를 측정합니다. 그리고 N번째 반복에서 사이클이 있는지 확인이 됩니다. 여기서 N번째 반복에서 0번에 사이클이 있다는 것이 확인될 것입니다. 하지만 아직 1번, 2번에는 그 사이클이 전파되었는지 알 수 없습니다. N + 1번째 반복을 실행한다면 사이클이 전파가 되어 이제 1번도 사이클이 있다는 것이 판단됩니다. 그리고 N + 2번째 반복이 되서야 2번에 사이클이 전파 되었음이 확인 됩니다. 

 

즉 이 문제는 기존처럼 N번 반복하는 것이 아니라 마지막 정점까지 전파가 되었음을 확인하기 위해 2 * N번 반복을 실행해야 시작 정점에서 끝 정점까지 사이클의 영향이 전파 되었는지 확인이 가능합니다. 만약 정점이 많아 2 * N번 반복하게 하는 것이 싫다면 사이클이 발생한 지점부터 도착 지점까지 연결이 되었는지 확인하는 BFS 코드를 넣는 것도 하나의 방법입니다.

 

코드 작성하기

그럼 같이 코드를 작성해 보도록 하겠습니다.

입력받기

mii = lambda : map(int, input().split())
N, S, E, M = mii()
INF = 1e9
arr = []
for _ in range(M):
    s, e, p = mii()
    arr.append([s, e, p])

start_price = list(mii())

도시의 수 N, 시작 도시 S, 도착 도시 E, 교통 수단의 개수 M을 입력 받습니다. 그리고 M개의 줄에 교통 수단의 정보를 입력 받습니다. 마지막으로 각 도시에서 벌 수 있는 돈의 최대값을 start_price라는 리스트에 넣었습니다.

금액 세팅

금액은 결국 벌 수 있는 돈에서 교통 수단에서 사용한 비용을 뺀 가격이 됩니다. 따라서 교통을 통해 이동을 할 때 드는 비용에 대한 수정이 들어가야 합니다.

for i in range(M):
    _, e, p = arr[i]
    p = -p + start_price[e]
    arr[i][2] = p

교통편 M개를 돌면서 수정을 진행합니다. 각 교통편의 가격을 확인하여 start_price 에서 교통비 p를 빼서 p에 넣어줍니다. 그러면 모든 교통편에 대해 도시를 방문하였을 때 벌 수 있는 금액에서 사용한 교통비가 제외되어 실제로 벌 수 있는 금액을 알 수 있습니다.

 

벨만 포드 알고리즘

def bellman_ford():
    prices = [-INF] * N 
    prices[S] = start_price[S]

    for i in range(N * 2):
        for s, e, p in arr:
            if prices[s] == -INF:
                continue
            nxt_price = prices[s] + p

            if prices[e] < nxt_price:
                prices[e] = nxt_price
                if i >= N:
                    prices[e] = INF
        print(prices)               
    if prices[E] == INF:
        print("Gee")
    elif prices[E] == -INF:
        print("gg")
    else:
        print(prices[E])

bellman_ford()

벨만 포드 알고리즘은 기본 벨만 포드 알고르즘과 크게 다르지 않습니다. 특히 위에서 언급한 골목길 문제와 거의 유사합니다. 몇가지 다른 점에 대해서 설명하겠습니다.

시작 위치

먼저 시작 위치에 대한 가격입니다. 우리는 지금까지 시작 위치의 가격을 0으로 하였습니다. 하지만 이 문제에서는 시작 가격이 0이 아닙니다. 왜냐하면 그 도시에 위치하고 있다면 start_price에서 정한 금액을 벌 수 있기 때문입니다. 거기다 교통편을 타지 않았기 때문에 교통비를 제외하지 않고 온전히 start_price에 대한 금액을 벌 수 있습니다.

반복 횟수

기존의 벨만 포드 반복 횟수는 정점의 개수만큼 N번 반복 하였습니다. N - 1번동안 최소 거리를 구하고 마지막 N번째 반복에서 음의 사이클을 판별하였습니다. 여기서는 음의 사이클의 전파를 확인하기 위해 총 2 * N번 반복을 합니다. 그래야 마지막 정점까지 음의 사이클이 전파가 되었는지 판단이 가능합니다. 

결과 출력

마지막으로 결과 출력을 해줍니다. 최종 도착지의 가격을 확인하여 무한대인 INF라면 Gee를, -INF라면 도착할 수 없기 때문에 gg를 출력합니다. 그리고 가격이 있다면 해당 가격을 출력해줍니다.

 

전체 코드

전체 코드를 확인해 보겠습니다.

mii = lambda : map(int, input().split())
N, S, E, M = mii()
INF = 1e9
arr = []
for _ in range(M):
    s, e, p = mii()
    arr.append([s, e, p])

start_price = list(mii())

for i in range(M):
    _, e, p = arr[i]
    p = -p + start_price[e]
    arr[i][2] = p

def bellman_ford():
    prices = [-INF] * N 
    prices[S] = start_price[S]

    for i in range(N * 2):
        for s, e, p in arr:
            if prices[s] == -INF:
                continue
            nxt_price = prices[s] + p

            if prices[e] < nxt_price:
                prices[e] = nxt_price
                if i >= N:
                    prices[e] = INF
        print(prices)               
    if prices[E] == INF:
        print("Gee")
    elif prices[E] == -INF:
        print("gg")
    else:
        print(prices[E])

bellman_ford()