백준 18352 : 특정 거리의 도시 찾기 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
INF=int(1e9)

def Dijkstra(start):

    dp=[INF]*(N+1) ; dp[start]=0
    heap=[]; heapq.heappush(heap,(0,start))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:
            next_value+=value

            if next_value<dp[next_node]:

                dp[next_node]=next_value
                heapq.heappush(heap,(next_value , next_node))

                if dp[next_node]==K:
                    Answer.append(next_node)


N,M,K,X=map(int,input().split())

graph=[ [] for _ in range(N+1) ]
for i in range(M):
    A,B=map(int,input().split())
    graph[A].append((1,B)) # 가중치를 모두 1로 고정한다.

Answer=[]

Dijkstra(X)
Answer.sort()


if not Answer:
    print(-1)
else:
    for i in Answer:
        print(i)

📌 어떻게 접근할 것인가?

다익스트라 알고리즘을 사용하였습니다. 모든 간선의 가중치가 1 이기 때문에 가중치는 1로 고정하고 단방향으로 이동하기 때문에 노드를 한방향으로만 추가해줍니다.

이후 최단경로를 찾으면서 만약 가중치의 합이 $K$ 인 지점이 발생하면 그때 Answer 리스트에 노드를 추가합니다.

단 이때 최단경로로 이동했을때 가중치의 합이 $K$ 임을 뜻합니다.

마지막으로 경우가 하나도 없을 경우는 $-1$ 을 출력하고 하나이상 존재하는 경우 노드의 번호를 오름차순으로 출력해줍니다.