[프로그래머스] 가장 먼 노드

문제 요약

n개의 노드가 있는 무방향 그래프가 주어진다.

각 노드는 1번부터 n번까지 번호가 붙어 있다.

목표는 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 것이다.

여기서 가장 멀리 떨어진 노드란, 1번 노드에서 최단 경로로 이동했을 때 지나야 하는 간선의 개수가 가장 많은 노드를 의미한다.

핵심 아이디어

이 문제는 1번 노드에서 모든 노드까지의 최단 거리를 구하면 된다.

간선의 가중치가 없고, 모든 간선의 이동 비용이 동일하므로 BFS를 사용하면 최단 거리를 구할 수 있다.

가중치 없는 그래프의 최단 거리 = BFS

BFS로 각 노드까지의 거리를 구한 뒤, 가장 큰 거리 값을 찾고 그 거리와 같은 노드의 개수를 세면 된다.

왜 BFS를 사용할까?

BFS는 시작 노드에서 가까운 노드부터 차례대로 방문한다.

따라서 처음 어떤 노드를 방문했을 때의 거리가 곧 최단 거리다.

예를 들어 다음 그래프를 생각해보자.

1 -- 2 -- 4
|    |
3 -- 5

1번 노드에서 시작하면 BFS는 다음 순서로 거리를 확정한다.

거리 0: 1
거리 1: 2, 3
거리 2: 4, 5

가장 먼 거리는 2이고, 해당 거리에 있는 노드는 4, 5이므로 답은 2다.

그래프 표현

간선은 양방향이다.

따라서 [a, b] 간선이 주어지면 a에서 b로도 갈 수 있고, b에서 a로도 갈 수 있다.

인접 리스트로 그래프를 만든다.

graph = [[] for _ in range(n + 1)]

for a, b in vertex:
    graph[a].append(b)
    graph[b].append(a)

노드 번호가 1번부터 시작하므로 배열 크기를 n + 1로 만든다.

거리 배열

각 노드까지의 최단 거리를 저장하는 배열을 만든다.

처음에는 아직 방문하지 않았다는 의미로 -1을 넣는다.

distance = [-1] * (n + 1)

시작 노드인 1번 노드의 거리는 0이다.

distance[1] = 0

BFS 과정

큐에는 현재 방문할 노드를 넣는다.

queue = deque([1])

큐에서 노드를 꺼낸 뒤, 연결된 다음 노드를 확인한다.

아직 방문하지 않은 노드라면 현재 노드의 거리보다 1 큰 값을 저장한다.

distance[next_node] = distance[current] + 1

그리고 다음 탐색을 위해 큐에 넣는다.

전체 코드

from collections import deque


def solution(n, vertex):
    graph = [[] for _ in range(n + 1)]

    for a, b in vertex:
        graph[a].append(b)
        graph[b].append(a)

    distance = [-1] * (n + 1)
    distance[1] = 0

    queue = deque([1])

    while queue:
        current = queue.popleft()

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

    max_distance = max(distance[1:])

    return distance.count(max_distance)

예제

n = 6
vertex = [
    [3, 6],
    [4, 3],
    [3, 2],
    [1, 3],
    [1, 2],
    [2, 4],
    [5, 2],
]

print(solution(n, vertex))

그래프를 그림으로 보면 다음과 같다.

      6
      |
1 --- 3 --- 4
|     |
2 ----
|
5

1번 노드에서 각 노드까지의 최단 거리는 다음과 같다.

노드	거리
1	0
2	1
3	1
4	2
5	2
6	2

가장 먼 거리는 2다.

거리 2에 있는 노드는 4, 5, 6으로 총 3개다.

실행 결과:

3

시간 복잡도

노드 수를 V, 간선 수를 E라고 하자.

인접 리스트를 만드는 데 O(E)가 걸린다.

BFS는 모든 노드와 간선을 한 번씩 확인한다.

O(V + E)

제한사항은 다음과 같다.

V <= 20,000
E <= 50,000

따라서 BFS로 충분히 해결할 수 있다.

공간 복잡도

인접 리스트와 거리 배열을 저장한다.

O(V + E)

정리

이 문제는 1번 노드에서 각 노드까지의 최단 거리를 구하는 문제다.

간선의 가중치가 없으므로 BFS를 사용하면 된다.

풀이 흐름은 다음과 같다.

1. 무방향 그래프를 인접 리스트로 만든다.
2. 1번 노드에서 BFS를 시작한다.
3. 각 노드까지의 최단 거리를 저장한다.
4. 가장 큰 거리 값을 찾는다.
5. 그 거리와 같은 노드의 개수를 반환한다.

가중치 없는 그래프 최단 거리 문제에서는 BFS를 먼저 떠올리는 것이 핵심이다.