백준 18352번 특정 거리의 도시 찾기

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

BFS 개념을 활용하면 풀 수 있는 흔한 문제이다.

from collections import deque
import sys
n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)




distance = [-1 for _ in range(n+1)]

def bfs(start):
    queue=deque()
    queue.append(start)
    distance[start] = 0
    while queue:
        city = queue.popleft()
        if distance[city] > k:
            break
        for i in graph[city]:
            if distance[i]==-1:
                distance[i] = distance[city]+1
                queue.append(i)

bfs(x)
if k not in distance:
    print(-1)
    sys.exit()
for i in range(len(distance)):
    if k == distance[i]:
        print(i)

대중적인 문제임에도 시간 초과를 5번은 넘게 본 것 같은데 처음엔 알고리즘을 잘못 짠 줄 알았다.
이유는 정말 단순하였는데...
문제를 보면 M(경로의 수)를 최대 1,000,000개를 입력받을 수 있어야 하는데
시간제한이 2초이므로 input()을 사용하면 시간 초과로 인하여 통과하지 못한다.
이 문제를 풀기 전까지는 계속해서 input( )을 사용하여 풀었기 때문에 이 점을 너무 간과하였다.

일정량 이상의 입력은 sys.stdin.readline(). rstrip()을 이용하여 받는다.

이 점만 주의하면 BFS 알고리즘을 사용하여 간단히 풀 수 있다.

추가적으로 readline() 뒤에 rstrip()를 붙이는 이유는 readline()을 사용하는 경우
이후의 "\n"까지 입력받기 때문이다.