BFS
너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘
동작원리 - 큐 / 구현 방법 - 큐 자료구조 이용

백준 18352번

✅ 문제

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

입력 예시 1

4 4 2 1
1 2
1 3
2 3
2 4

출력 예시 1

4

입력 예시 2

4 3 2 1
1 2
1 3
1 4

출력 예시 1

-1

내가 접근한 방식

DFS로 접근하여 재귀함수를 이용하였다.
예시는 제대로 출력되었지만 시간 초과, recursion error 발생하였다

N, M, K, X = map(int, input().split())

graph = [[] for _ in range(N+1)]
least_distance = [M] * (N+1)
visited = [False] * (N+1)

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

def dfs(graph, v, visited, count):
    visited[v] = True
    least_distance[v] = count
    count += 1
    for i in graph[v]:
        if visited[i] == True:
        	# 여기서 최단 거리 저장
            least_distance[i] = count
            break
        dfs(graph, i, visited, count)
    count = 0

dfs(graph, X, visited, 0)

if K not in least_distance:
    print(-1)
else:
    for i in range (1, len(least_distance)):
        if least_distance[i] == K:
            print(i)

➕ 문제 해설

'모든 도로의 거리는 1'이라는 조건 덕분에 너비 우선 탐색(BFS)을 이용하여 간단히 해결

from collections import deque

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)

# 방문 하지 않은 도시는 -1로 표시(distance[0]은 사용하지 않음)
distance = [-1] * (N+1)
distance[X] = 0

queue = deque()
queue.append(X)

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

if K not in distance:
    print(-1)
else:
    for i in range(len(distance)):
        if distance[i] == K:
            print(i)