특정 거리의 도시 찾기

---

13852

어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하라. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

입력:
도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
M개의 줄에 걸쳐 두 개의 자연수 A,B (공백으로 구분): A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미이다. (A와 B는 서로 다른 자연수)
출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력
도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력

풀이

---

출발 노드에서 각 노드로 향하는 최단 거리를 계산한 후, K인 노드를 출력하는 형식으로 해볼까 한다.

DFS를 사용

재귀함수를 사용하였더니 RecursionError 발생
ㅠㅠ

'''
특정 거리의 도시 찾기
'''

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)


def dfs(graph, start, visited, end):
    if end in graph[start]:
        return 1
    visited[start] = True
    for i in graph[start]:
        if not visited[i]:
            tmp = dfs(graph, i, visited, end)
            if tmp != 0:
                return 1 + dfs(graph, i, visited, end)
    return 0


answer = [0] * (n + 1)

for i in range(1, n + 1):
    if i == x:
        continue
    visited = [False] * (n + 1)
    visited[0] = True
    answer[i] = dfs(graph, x, visited, i)

print(answer)
for i,val in enumerate(answer):
    if val == k:
        print(i)
if k not in answer:
    print(-1)

풀이

---

모든 도로의 거리는 1이라는 조건을 이용하여 너비 우선 탐색을 이용

import sys
from collections import deque
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)


distance = [-1] * (n+1)
distance[x] = 0

q = deque()
q.append(x)
while q:
    now = q.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            q.append(next_node)


for i,val in enumerate(distance):
    if val == k:
        print(i)
if k not in distance:
    print(-1)