백준 문제 풀이 - 특정 거리의 도시 찾기 18352번

📜 문제 이해하기

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

💡 문제 재정의

방향 그래프에서 x번째 노드에서 최단거리가 k인 노드를 모두 출력하여라

✏️ 계획 수립

최소 스패닝 트리를 활용하면 문제를 풀 수 있다.
최소 스패닝 트리를 확장해가면서 k일때까지만 트리를 확장한다.
그 후 k가 넘어가면 반복문을 중단하고 k인 노드들을 모두 출력한다.

💻 계획 수행

import sys

distance = []
adj_list = []
node_state = []


if __name__ == '__main__':
    N, M, K, X = map(int, sys.stdin.readline().split())
    d = 0
    adj_list = [[] for _ in range(N + 1)]
    distance = [300001 for _ in range(N + 1)]
    node_state = ['U' for _ in range(N + 1)]
    result = []

    for _ in range(M):
        city1, city2 = map(int, sys.stdin.readline().split())
        adj_list[city1].append(city2)

    node_state[X] = 'T'
    distance[X] = d
    for adj_node in adj_list[X]:
        node_state[adj_node] = 'F'

    while 'F' in node_state:
        d += 1
        if d > K:
            break
        fringe_node = []
        for i, state in enumerate(node_state):
            if state == 'F':
                fringe_node.append(i)
        for node in fringe_node:
            node_state[node] = 'T'
            distance[node] = d
            if d == K:
                result.append(node)
            for adj_node in adj_list[node]:
                if node_state[adj_node] == 'U':
                    node_state[adj_node] = 'F'

    if not result:
        print(-1)
    else:
        print(*result, sep='\n')

🤔 회고

최단 거리 알고리즘을 알 수 있어야 풀 수 있는 문제이다.
최소 스패닝 트리가 아닌 다익스트라를 활용해도 풀 수 있다.