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

문제

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

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

 

문제 풀이

단방향 그래프에서 최단거리 찾기 위해 bfs 돌림. visited를 따로 두고 풀었는데, 다른 분들 풀이 보니까 그냥 각 노드에 대한 distance 배열을 만들어서 최단거리로 차차 갱신하며 푸는 법이 일반적 + 더 효율적인듯

 

코드

import sys
input = sys.stdin.readline
import collections

N, M, K, X = map(int,input().split())
MAP = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    MAP[A-1].append(B-1)

q = collections.deque()
q.append((X-1,0))

res = set()
visited = [0 for _ in range(N)]
visited[X-1] = 1
while q:
    cur_idx, cnt = q.popleft()
    if cnt == K:
        res.add(cur_idx+1)
    if cnt == K+1:
        break

    for n_idx in MAP[cur_idx]:
        if visited[n_idx] == 0:
            q.append((n_idx, cnt + 1))
            visited[n_idx] = 1
    
if not res:
    print(-1)
else:
    print(*sorted(res), sep='\n')