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

백준 특정 거리의 도시 찾기 문제 풀이이다.

어떤 나라에는 N개의 도시와 M개의 단방향 도로가 존재하며, 모든 도로의 거리는 1이다.

이때, 특정 도시 X에서 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 문제이다.
(도시 X에서 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.)

예시를 하나 보자.

위의 그래프에서 N = 4, K = 2, X = 1일 때, 정답은 4이다.
왜냐하면 출발 도시 X에서 도달할 수 있는 도시(1, 2, 3, 4) 중 최단 거리가 2인 도시는 4가 유일하기 때문이다.

그래프 문제이기도 하고, 최단 거리를 찾는 문제이므로 BFS로 접근할 수 있다.

도시 x에서 시작해서 인접한 노드를 BFS로 탐색하면서, 처음 방문하는 노드의 경우 최단 거리(shortest_dist)를 업데이트하면 된다.

출력은 flag라는 변수를 활용하여, x에서 각 노드까지의 최단 거리가 k인 노드를 전부 출력하고, 그런 노드가 하나도 없다면 -1을 출력한다.

코드(정답)는 다음과 같다.

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

visited = [False] * (n + 1)
shortest_dist = [0] * (n + 1)

# BFS
queue = deque([x])
visited[x] = True
while queue:
    now = queue.popleft()

    # 인접 노드 탐색
    for next in graph[now]:
        # 아직 방문하지 않은 노드만 고려
        if not visited[next]:
            # 해당 노드 방문 처리
            queue.append(next)
            visited[next] = True

            # 해당 노드까지의 최단 거리 업데이트
            shortest_dist[next] = shortest_dist[now] + 1

# 출력
flag = False
for i in range(1, n + 1):
    if shortest_dist[i] == k:
        print(i)
        flag = True

if not flag:
    print(-1)