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

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

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

import sys
from collections import deque
 
input = sys.stdin.readline
 
n, m, k, x = map(int, input().split())
visited = [False] * (n + 1)
 
path = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    path[a].append(b)
 
answer = list()
q = deque()
q.append((x, 0))
while q:
    town, count = q.popleft()
    if count == k:
        answer.append(town)
    elif count < k:
        for con in path[town]:
            if not visited[con]:
                visited[con] = True
                q.append((con, count + 1))
 
if len(answer) == 0:
    print(-1)
else:
    answer.sort()
    for ans in answer:
        print(ans)

전형적인 BFS문제이다.

시작점에서부터 연결된 마을을 추가하며, 원하는 거리의 도시를 따로 저장한 후, 출력한다.

가장 중요한 점은, 파이썬의 경우 input().split()으로 하면 입력량이 많기 때문에 시간 초과가 난다.

sys.stdin.readline()을 사용해야 한다.