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

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

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

import sys; input = sys.stdin.readline
from collections import deque
N, M, K, X = map(int, input().split())
linked_list = [list() for _ in range(N + 1)]
for i in range(M):
    s, e = map(int, input().split())
    linked_list[s].append(e)

visit = [K + 1 for _ in range(N + 1)]
visit[X] = 0

q = deque()
q.append(X)
while q:
    cur = q.popleft()
    for adj in linked_list[cur]:
        if visit[adj] != K and visit[adj] > visit[cur] + 1:
            visit[adj] = visit[cur] + 1
            q.append(adj)

ans = ''
for i in range(N + 1):
    if visit[i] == K:
        ans += str(i)+'\n'

print(ans if ans else -1)

연결리스트로 단방향 그래프를 작성하였고 다익스트라를 사용하였다.

visit으로 방문 하지 않은 노드 중에 갱신될만한 곳을 찾아서 큐에 넣었고 끝날때까지 반복한다.

반복문이 끝난 이후 특정 거리의 도시번호를 추가하고 없는 경우엔 -1을 출력하였다.

 

오랜만에 실버 문제여서 쉽게 풀었다.