우선순위가 2개 이상인 다익스트라 알고리즘 연습

1. 문제1

 

16167번: A Great Way (acmicpc.net)

16167번: A Great Way

 

2. 풀이

 

다익스트라 알고리즘으로 최단거리만을 요구하는 문제가 기본문제고,

 

최단거리면서, 그러한 거리가 여러개인 경우 거쳐가는 노드가 최소가 되는 경로를 찾으라고 한다면?

 

접근 방법은 distance 배열 설정을 조금만 바꿔주면 된다

 

distance[v]를 출발점에서 v까지 가는데 가는 [비용, 거친 노드 수]로 정의해주자

 

"비용이 먼저 최소가 되면서, 비용이 서로 동일하면 노드 수가 최소가 되어야한다"

 

INF = 1000000000000000000000000000

queue = []

distance = [[INF,INF] for _ in range(n+1)]

heapq.heappush(queue,(0,1,1))

distance[1] = [0,0]

 

시작점은 1번이니까, distance[1]은 [0,0]으로 초기화

 

시작점에서 시작점으로 가는 비용은 0이고 거친 노드도 0이니까

 

이 문제는 그래프 설정이 조금 특이한데, 10분간 기본 비용과 1분당 추가 비용, 도착 노드까지 가는 시간이 모두 제시된다

 

그러면 그래프를 설정할때, 10분간 기본 비용 + 1분당 추가비용으로 도착노드까지 가는 시간에 따른 비용을 계산해서,

 

graph[출발노드].append((비용, 도착노드))로 해준다

 

가는 시간이 10분 이하이면, 기본 비용만 내주면 될거고, 10분 넘는다면, 기본비용 + (남는시간)*추가비용으로 내준

 

import heapq
from sys import stdin

n,r = map(int,stdin.readline().split())

graph = [[]*(n+1) for _ in range(n+1)]

for _ in range(r):
    
    a,b,c,d,e = map(int,stdin.readline().split())

    if e <= 10:
        
        cost = c
    
    else:
        
        cost = c + (e-10)*d

    graph[a].append((b,cost))

 

이제 queue를 순회하면서 다익스트라 알고리즘을 수행하면 된다

 

queue에서 꺼낸 dist가 distance[v][0]보다 크다면, 이미 v까지 distance가 갱신된 상태이니 continue로 넘겨주고

 

그렇지 않다면, v와 연결된 graph[v] 노드들을 모두 순회해본다.

 

u까지의 cost는 dist + c일테고, distance[u][0]보다 cost가 작다면, cost를 갱신해주고

 

거친 노드 수는 v에서 u로 가면 노드 1개를 더 거치니까, count + 1일것이다. 이를 distance[u][1]에 넣어준다.

 

하지만 distance[u][0]와 cost가 동일하다면, 거친 노드수가 작아야하므로, distance[u][1]과 count+1을 비교해서,

 

count+1이 더 작다면 distance[u][1]을 갱신해주고, 우선순위 큐에 넣어준다

 

while queue:
    
    dist,count,v = heapq.heappop(queue)

    if distance[v][0] < dist:
        
        continue
    
    for u,c in graph[v]:
        
        cost = dist + c

        if distance[u][0] > cost:
            
            distance[u][0] = cost
            distance[u][1] = count+1

            heapq.heappush(queue,(cost,count+1,u))
        
        elif distance[u][0] == cost:
            
            if distance[u][1] > count+1:
                
                distance[u][1] = count+1

                heapq.heappush(queue,(cost,count+1,u))

 

반복이 끝나고도 distance[도착점][0]가 INF라면, 도착점으로 도달 못한다는 뜻

 

if distance[n][0] == INF:
    
    print('It is not a great way.')

else:
    
    print(distance[n][0], distance[n][1])

 

 

3. 문제2

 

9893번: Paths (acmicpc.net)

9893번: Paths

 

4. 풀이

 

이 문제는 조금 다르게 거쳐가는 경로의 수를 최소화시키면서, 거쳐가는 경로의 수가 동일하다면, 비용의 합을 최소화시켜야한다

 

접근하는 방법은 동일하다

 

distance[v]를 v까지 가는데 [거쳐가는 경로의 수, 비용]으로 정의

 

최소를 찾아야하니 INF를 적당히 정의하고, [INF,INF]를 원소로 가지도록 초기화

 

출발점 0에 대하여 distance[0] = [0,0]으로 정의

 

출발점에서 출발점까지 거쳐가는 경로의 수는 0이고, 비용도 0이니까

 

우선순위 큐에서 (거쳐가는 경로의 수, 비용, 다음 노드)를 하나씩 빼면서 순회

 

distance[v][0]가 거쳐가는 경로의 수 count보다 작다면, 이미 갱신된거니까 continue로 넘겨주고

 

그렇지 않다면 v와 연결된 노드 graph[v]를 모두 순회

 

비용의 합 cost = dist + c일테고, 거쳐가는 경로의 수는 1씩 증가할테니 count+1

 

거쳐가는 경로의 수가 제 1 우선순위니까, distance[v][0]가 count+1보다 크다면, count+1로 갱신해주고,

 

비용 distance[v][1]도 cost로 갱신해줘야지

 

하지만 거쳐가는 경로의 수가 동일하다면, 다음 우선순위는 비용이니까 distance[v][1]과 cost를 비교해서

 

cost가 더 작다면 갱신해준다

 

import heapq
from sys import stdin

INF = 100000000000000000000000000000000000

m,n = map(int,stdin.readline().split())

graph = [[] * (m) for _ in range(m)]

for _ in range(n):
    
    u,v,c = map(int,stdin.readline().split())

    graph[u].append((v,c))

queue = []

distance = [(INF,INF) for _ in range(m+1)]

distance[0] = (0,0)

heapq.heappush(queue,(0,0,0))

while queue:
    
    count,dist,v = heapq.heappop(queue)

    if distance[v][0] < count:
        
        continue
    
    for u,c in graph[v]:
        
        cost = dist + c

        if distance[u][0] > count+1:
                
            distance[u] = (count+1,cost)

            heapq.heappush(queue,(count+1,cost,u))
        
        elif distance[u][0] == count+1:
            
            if distance[u][1] > cost:
                
                distance[u] = (count+1,cost)

                heapq.heappush(queue,(count+1,cost,u))

print(distance[1][1])

 

도달 불가능한 경우는 없나???

 

문제에서 그런말은 없기는 한디..

 

 

5. 문제3

 

13290번: Big Truck (acmicpc.net)

13290번: Big Truck

 

6. 풀이

 

이 문제는 출발점에서 도착점으로 가는 가장 비용이 작은 경로를 찾는데,

 

비용이 동일한 경로라면, 거쳐간 노드가 가지고 있는 아이템의 수 합이 최대가 되는 경로를 찾는 문제

 

특이하게 노드가 가지고 있는 아이템이 제시되는데, 그래프를 설정할때..

 

a번 노드에서 b번 노드로 가는 비용이 c이고, b번 노드가 보유한 아이템이 d이면...

 

graph[a].append((b,c,d))를 넣어주면 될 것이다

 

import heapq
from sys import stdin

n = int(stdin.readline())

items = list(map(int,stdin.readline().split()))

graph = [[]*(n+1) for _ in range(n+1)]

m = int(stdin.readline())

for _ in range(m):
    
    a,b,d = map(int,stdin.readline().split())

    graph[a].append((b,d,items[b-1]))
    graph[b].append((a,d,items[a-1]))

 

 

다음 distance를 설정하는데 distance[i]를 i까지 도달하는데 [걸리는 비용, 획득한 아이템 수 합]으로 정의

 

출발점 distance[1]은 [0,items[0]]로 정의

 

왜냐하면 1번에서 1번으로 가는 비용은 0일것이고, 집어간 아이템 수는 1번이 가진 아이템 수일테니까

 

queue = []

INF = 10000000000000000000000

distance = [[INF,0] for _ in range(n+1)]

distance[1] = [0,items[0]]

heapq.heappush(queue,(0,items[0],1))

 

우선순위 큐에서 (비용, 아이템 수, 노드)를 하나씩 빼서 순회해가지고, 제1 우선순위인 distance[v][0]가 dist보다 작다면..

 

continue로 넘겨주고..

 

그렇지 않다면 v에 연결된 graph[v]를 모두 순회해서..

 

cost를 계산하는데 cost = dist + c이고 집어간 아이템 수도 비교에 필요하니 pick = item + i로 더해준다

 

제1우선순위 비용 cost가 distance[u][0]보다 작다면, distance[u][0]를 갱신해주고.. 집어간 아이템 수 distance[u][1]도 pick으로 갱신

 

cost가 동일하다면.. 집어간 아이템 수 pick이 최대가 되어야하므로, distance[u][1]이 pick보다 작다면.. distance[u][1]을 pick으로 갱신

 

반복문이 끝나고 나서 distance[도착점][0]가 INF이면 도달 불가능이고, 그렇지 않다면 도달 가능일것이다.

 

while queue:
    
    dist,item,v = heapq.heappop(queue)

    if distance[v][0] < dist:
        
        continue
    
    for u,c,i in graph[v]:
        
        cost = dist + c
        pick = item + i

        if distance[u][0] > cost:
            
            distance[u][0] = cost
            distance[u][1] = pick
            heapq.heappush(queue,(cost,pick,u))
        
        elif distance[u][0] == cost:
            
            if distance[u][1] < pick:
                
                distance[u][1] = pick
                heapq.heappush(queue,(cost,pick,u))
    
if distance[n][0] == INF:
    
    print("impossible")

else:
    
    print(distance[n][0], distance[n][1])