문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

import sys

sys.setrecursionlimit(1000000000)

n, m, k, x = map(int, sys.stdin.readline().rstrip().split())
graph = []
for _ in range(n):
  graph.append([])
for _ in range(m):
  a, b = map(int, sys.stdin.readline().rstrip().split())
  graph[a - 1].append(b - 1)


def dfs(v, road, count):
  if road[v] > count:
    road[v] = count
    if count < k:
      for i in graph[v]:
        dfs(i, road, count + 1)


road = [300001] * n
dfs(x - 1, road, 0)

if k in road:
  for i in range(n):
    if road[i] == k:
      sys.stdout.write(str(i + 1) + "\n")
else:
  sys.stdout.write("-1\n")

시간 초과 : sys.stdin.readline()

메모리 초과 : pypy3 -> Python 3

런타임 에러 (RecursionError) : sys.setrecursionlimit(1000000000)

dfs로 구현할 경우 예외처리를 통해 시간과 메모리를 절약해야 한다.

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