[백준]5214 환승

1.풀이

거쳐가는 노드수의 최솟값을 계산해야한다. 하이퍼튜브는 k가지 노드를 모두 연결해주는, 즉 1의 가중치를 가지게 해주는 장치이다. 따라서 아래와 같이 가중치를 주면 하이퍼튜브를 통해서 노드를 연결해주는 그래프를 만들 수 있다.

노드 -> 하이프튜브 : 가중치 1

하이퍼튜브 -> 노드 : 가중치 0​

이렇게 하면 (노드a->하이퍼튜브->노드b) 의 cost가 1이 되어서 다익스트라 처럼 풀 수 있다.

​

2.소스코드

import heapq

maxNum=9876543210
N,K,M=map(int,input().split())
graph={}
for i in range(1,N+M+1):
    graph[i]=[]
for i in range(M):
    temp=list(map(int,input().split()))
    for k in range(K):
        graph[N + i + 1].append([0, temp[k]])
        graph[temp[k]].append([1, N + i + 1])

nodeDist=[maxNum for i in range(N+M+1)]
nodeDist[1]=1
dij=[[1,1]]
ans=-1
while(dij):
    nowCost,nowNode=heapq.heappop(dij)
    if nowNode==N:
        ans=nowCost
        break
    if nodeDist[nowNode]<nowCost:
        continue
    for addedCost,toNode in graph[nowNode]:
        toCost=addedCost+nowCost
        if toCost<nodeDist[toNode]:
            nodeDist[toNode]=toCost
            heapq.heappush(dij,[toCost,toNode])
print(ans)