[BOJ] 18352 특정 거리의 도시 찾기

from collections import deque

def bfs(x):
    queue = deque()
    queue.append(x)
    distance[x] = 0
    while queue:
        now = queue.popleft()
        for next_node in graph[now]:
            if visited[next_node] == False:
                visited[next_node] = True
                if distance[next_node] == -1:
                    distance[next_node] = distance[now] + 1
                    queue.append(next_node)
                
                

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)
visited = [False] * (n + 1)

bfs(x)

result = []
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        result.append(i)
        check = True
if len(result):
    for i in range(len(result)):
        print(result[i])
else:
    print(-1)

 기초적인 다익스트라 문제이고, 다익스트라를 모르더라도 BFS를 아는 것만으로 풀 수 있다.

이 문제를 풀 시기에 다익스트라를 몰랐고, 현재도 다익스트라를 배웠지만 자주 안 쓰다보니 까먹었다!(다시 공부해야한다.)

 

이 문제는 단 방향 그래프이고, 방문 여부와 거리를 저장하기 위한 리스트를 만들어주었다.

bfs 를 통해 현재 위치에서 최단거리를 구하고, 이동거리를 저장하고 주어진 K와 같은 노드들을 출력해주면 된다.