특정 거리의 도시 찾기

 

문제

노드의 수(N), 간선의 수 (M), 출발 도시의 번호(X) 가 주어질 때,

노드 X로 부터 거리가 K인 노드 번호를 모두 구하라.

 

 

 

유형 분석 및 해결

- 노드와 간선 그래프이다.

- 거리가 모두 1이다.

- 특정노드와 거리가 k인 노드

-> BFS

 

 

 

코드

from collections import deque
def solution(n, k, x, array):
    distance = [-1]*(n+1)
    distance[x] = 0
    queue = deque()
    queue.append(x)
    while queue:
        now= queue.popleft()
        for i in array[now]:
            if distance[i] == -1:
                distance[i] = distance[now] + 1
                queue.append(i)
    result = []
    for i in range(len(distance)):
        if distance[i] == k:
            result.append(i)
    return result





n, m, k, x = 4, 4, 1, 1
array = [
    [],
    [2, 3],
    [3, 4],
    [],
    []
]
result = solution(n, k, x, array)
if len(result) == 0:
    print("-1")
else:
    for i in result:
        print(i)

 

구현

방문처리 -> distance가 -1이 아니라면 방문한 것

distance : 노드 x와의 거리

 

 

시간 복잡도

최대 노드의 수 30만, 간선 100만 -> O(N+M) : 130만회의 연산

DFS/BFS -> O(N)