백준(11657,1219)

벨만포드 알고리즘

타임머신으로 빨리가기(11657)

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

• 입출력 예시

3 4
1 2 4
1 3 3
2 3 -1
3 1 -2

--------------

4
3

해결책

이 문제는 출발점으로부터 갈 수 있는 모든 노드의 최단경로를 구하는 기본적인 문제이다.

대표적인 그래프 최단경로 알고리즘인 다익스트라와 플로이드를 떠올릴 수 있지만, 이문제에는 제약사항이 있다. 바로, 음수 가중치를 갖는 간선이 있다는 것이다. 그러므로 음수간선을 반영할 수 있는 벨만포드 알고리즘으로 해결해야한다.

벨만포드 알고리즘은 2가지로 구성되어있다. (노드개수 : N, 간선개수 : M, 출발점 : S)

첫번째는 음수 사이클이 없다고 가정했을때 나오는 최단경로 값을 기록,

두번째는 음수 사이클이 존재하다면, 한없이 최단경로값이 작아질것이기 때문에, 이때는 -1을 출력해줘야한다.

첫번째

1. [출발, 도착, 가중치]의 간선정보를 리스트에 저장한다.

2. 루프를 돌면서 N-1번 순회한다. ( N-1은 시작점을 제외한 모든 노드의 경로가 반영될 수 있도록)

   2.1 간선의 개수 M만큼 이중 루프를 돈다.

   Dist[end] > Dist[start]+ Line[반복변수][2] 이라면, Dist[end]를 변경한다.

두번째

1. 간선의 개수 M만큼 루프를 돌면서,

   Dist[end] > Dist[start]+ Line[반복변수][2] 이라면, 이는 사이클이 존재하기때문에 빠져나와야한다.

코드

import sys
input = sys.stdin.readline

n,m = map(int ,input().split())

dist=[sys.maxsize]*(n+1)

line = []

for i in range(m):
    s,e,w = map(int,input().split())
    line.append([s,e,w])

    
dist[1]=0
# start node is number 1

# 벨만포드는 간단하다 . 시작점을 제외시킨후 노드들의 경로를 조사하면
# 모든 경로값이 최단으로 나올 수 있다.
# 물론 사이클이 존재하면 안된다.

for i in range(n):
    for j in range(m):
        pnode=line[j]
        start = pnode[0]
        end = pnode[1]
        weight = pnode[2]

        if dist[start]!= sys.maxsize and dist[end] > dist[start]+weight:
            dist[end] = dist[start]+weight

# 사이클 존재유무는 n-1번 루프 수행 후, 확인해준다.

cycle = False

for i in range(m):
    
    pnode=line[i]
    start = pnode[0]
    end = pnode[1]
    weight = pnode[2]

    if dist[start]!= sys.maxsize and dist[end] > dist[start]+weight:
        cycle = True
        break
            

if cycle:
    print("-1")
else :
    for i in range(2,n+1):
        if dist[i]!=sys.maxsize:
            print(dist[i])
        else:
            print("-1")

세일즈맨의 고민(1219)

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

오민식은 고민에 빠졌다.

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

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다.

오민식이 이용할 수 있는 교통수단은 여러 가지가 있다. 오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다. 이 값은 도시마다 다르며, 액수는 고정되어있다. 또, 도시를 방문할 때마다 그 돈을 벌게 된다.

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

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

• 입력

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

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

• 출력

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

• 입출력 예시

5 0 4 5
0 1 10
1 2 10
2 3 10
3 1 10
2 4 10
0 10 10 110 10

--------------

Gee

해결책

이 문제 또한 세일즈맨의 이곳저곳을 순회하고, 도착지에 도달해야만 한다는 점에서 최단경로 문제와 비슷해보이지만, 이 문제가 원하는 요구는 세일즈맨이 어디를 가든 상관없지만, 도착지에 도달하고 챙길 수 있는 최대이익에 대해서 묻고있다. 그러므로, 위의 벨만포드알고리즘의 조건식을 조금 변경하여 사용 할 수 있겠다.

예를 들어 위의 입력 예시에서 본다면 2번노드에서 3번노드로 오민식이 이동한다고 가정할 때 3번의 도시기회비용이 110이고, 2→3 이동비용이 10이므로, 2번에서 계산되었던 비용 + 도시비용 - 이동비용으로 수정될 수 있다는 것이다.

또 주의할 점으로는 만약 양의 사이클이 존재하다면, 무한으로 이익을 취할 수 있는 경우도 문제에서 요구한다. ( 문제의 가중치값에는 음수가중치가 없다. 그러므로 음의 사이클을 일어날 수 없다.)

이것을 캐치 할 수 있도록, 조건문을 잘 구성해야한다.

조건1. 초기화가 되긴했니?

Elif조건. 출발값이 사이클인거 아니야?

Elif조건. dist[end] < dist[start] + value[end] - lines[j][2]인거야?

조건. n-1을 초과했니? (양의 사이클이냐?)

dist[end] = sys.maxsize

Else

dist[end]=dist[start] + value[end] - lines[j][2]

코드

import sys
input = sys.stdin.readline

#시작노드는 0번 노드이다.

n,starter,ender,m = map(int,input().split())

line = []

dist=[-sys.maxsize]*(n+1)

for i in range(m):
    s,e,w = map(int,input().split())

    line.append([s,e,w])

value=list(map(int,input().split()))

# value는 노드를 방문했을때 얻는 값입니다.

dist[starter] =value[starter]

for i in range(n+100):
    for j in range(m):
        pnode=line[j]
        start = pnode[0]
        end = pnode[1]
        weight = pnode[2]
        

        if dist[start]== -sys.maxsize :
            continue
        elif dist[start] == sys.maxsize:
            dist[end]=sys.maxsize
        elif dist[end]<dist[start]+value[end]-weight:
            if i >n-1:
                dist[end]=sys.maxsize
            else :
                dist[end]=dist[start]+value[end]-weight
                
            
            

if dist[ender] == sys.maxsize :
    print("Gee")
elif dist[ender] == -sys.maxsize:
    print("gg")
else :
    print(dist[ender])