[백준/python] 18352번: 특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기 (acmicpc.net)

18352번: 특정 거리의 도시 찾기

단순 다익스트라 문제. 늘 풀던 것과는 다르게 거리정보 없이 그냥 1. graph리스트에 방향정보를 저장. dist리스트에 출발노드에서의 거리를 모두 저장

~다익스트라 이용 : 힙큐모듈이용 q 리스트 생성. 출발노드 저장. dist에 출발노드는 거리 0 저장. while 반복문으로 q 끝날때까지 돌기! q에서 거리정보가장작은애 pop 해주며 distance와 now에 저장. 만일 distance가 dist[now]보다 크다면... 이미 방문한 것이므로 continue. now의 인접노드를 확인하기위해 그래프의 정보대로 for문 돌기. 이때 인접노드들이 dist에 저장된 정보가 distance+1보다 크다면 == 출발노드에서 now를 거쳐 이 노드로 가는 거리가 더 짧다면 dist 갱신! 그리고 q에 거리정보와 함께 삽입. 이를 q 끝날 때까지 반복~

다익스트라 호출해주고 저장된 dist리스트를 전부 읽으며 k와 같다면 출력 아니라면 -1 출력.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

import heapq

n,m,k,x=map(int,input().split()) #도시개수,도로개수,거리,출발
graph=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)

INF=int(1e9)
dist=[INF]*(n+1)
def dijkstra(start):
    q=[]
    heapq.heappush(q,(0, start))
    dist[start]=0

    while q:
        distance, now= heapq.heappop(q)
        if distance> dist[now]: continue
        for i in graph[now]:
            cost= distance + 1
            if cost< dist[i]:
                dist[i]=cost
                heapq.heappush(q,(cost, i))

dijkstra(x)
ans=0
for i in range(1, n+1):
    if dist[i]==k:
        print(i)
        ans+=1
if ans==0: print(-1)