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

윤무무 2023. 3. 20. 18:26

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

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

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

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)

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

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