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

https://www.acmicpc.net/problem/18352

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

 

1. 난이도 실버2

 

2. 내가 작성한 풀이

from collections import deque
import sys
input = sys.stdin.readline

INF = int(1e9)

n, m, k, x = map(int, input().rstrip().split())

distance = [INF] * (n+1) #최단거리 저장
distance[x] = 0
maps = [[] for _ in range(n+1)] #그래프 관계 저장

for i in range(m):
    a,b = map(int, input().rstrip().split())
    maps[a].append(b)

queue = deque()
queue.append(x)

while queue: 
    popX = queue.popleft()
    for i in maps[popX]:
        if distance[i] > distance[popX] + 1:
            distance[i] = distance[popX] + 1
            queue.append(i)

cnt = False

for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        cnt = True

if cnt == False:
    print(-1)

 

다익스트라 알고리즘을 이용해서 문제를 풀었다.

 

토익스피킹 공부하느라 코테에 소홀했더니 다~~까묵었네