문제

https://school.programmers.co.kr/learn/courses/30/lessons/68937

풀이

트리

트리에서 임의로 고른 세 점 사이의 세 거리 중, 중간값을 가장 크게 만드는 경우를 구하는 문제이다.

처음에는 입력이 트리라는 점을 놓치고 일반적인 그래프 탐색 문제로 접근하려 했다. 하지만 노드의 개수가 최대 $250,000$개이므로, 모든 노드를 시작점으로 탐색하거나 노드 쌍을 직접 확인하는 $O(n^2)$ 방식은 불가능하다고 판단했다.

이후 문제를 다시 읽으며 입력이 트리임을 확인했고, 트리의 특성을 최대한 활용하는 방향으로 접근을 바꾸었다.

이 문제에서 활용할 수 있는 트리의 주요 특성은 다음과 같다.

• 트리는 사이클이 없는 연결 그래프이다.
• 트리의 간선 개수는 노드 개수보다 항상 1개 적다.
• 트리의 임의의 두 노드 사이에는 단 하나의 경로만 존재한다.
• 어떤 노드를 루트로 선택해도 트리의 연결성과 비순환성은 유지된다.

특히 어떤 노드를 루트로 선택해도 트리가 유지된다는 점을 토대로 아이디어를 떠올렸다.

중간값의 최댓값

우선 중간값의 최댓값을 구한다는 것부터 살펴보았다. 중간값을 가장 크게 만들려면 어떻게 해야 할까? 중간값을 가장 크게 만들려면 세 거리 중 가장 큰 값이 가장 커져야 한다. 그럼 가장 큰 값의 최댓값은 어떻게 될까? 생각이 여기까지 흘렀을 때쯤, 트리의 지름을 이용해 풀 수 있는 문제라는 것을 알게 되었다.

경우의 수

트리의 지름은 트리 안의 임의의 두 점 사이 거리 중 최댓값이다.

트리의 지름을 $D$라고 하면, 세 점 사이에서 만들어지는 모든 거리는 $D$를 넘을 수 없다. 따라서 세 거리의 중간값 역시 $D$보다 클 수 없다.

결론부터 말하면, 중간값의 최댓값은 지름의 길이인 $D$ 또는 $D-1$이다.

중간값이 $D-1$인 경우

지름의 양 끝 노드를 선택하고, 지름 경로에서 한쪽 끝 노드에 인접한 노드를 선택하면 세 점 사이의 거리는 다음과 같은 형태가 된다.

[ '1', 'D-1', 'D' ]

트리의 지름은 항상 존재하고 인접한 노드 또한 반드시 존재하므로 중간값이 $D-1$이 되는 경우는 항상 존재한다.

중간값이 $D$인 경우

중간값이 $D$가 되려면 세 거리 중 적어도 두 개가 $D$여야 한다. 즉, 해당 트리의 지름이 두 개 이상 존재하는 경우에만 중간값이 $D$가 될 수 있다. 이때 세 점 사이의 거리는 다음과 같은 형태가 된다.

[ 'X', 'D', 'D' ]

X가 어떤 값이든 중간값은 $D$이다.

정리하면 다음과 같다.

어떤 지름 끝 노드에서 거리가 $D$인 노드가 두 개 이상 존재하면 정답은 $D$이다. 지름의 양쪽 끝 노드 모두 최원거리 노드가 하나뿐이라면 정답은 $D-1$이다.

트리의 지름

이제 문제는 트리의 지름과 지름의 양 끝 노드를 구하는 일로 귀결된다.

트리의 지름은 어떻게 구할까? 임의의 한 점을 선택해 그 점에서 가장 먼 점을 구한다. 이후 그 점에서 다시 가장 먼 점을 구하면, 두 점 사이의 거리가 트리의 지름이 된다.

이를 기하학적인 관점에서 직관적으로 이해해 보자.

'지름'이라고 하면 원이 떠오른다. 트리를 간선이 서로 교차하지 않도록 쫙 펴서 평면에 그리고, 트리의 지름 경로를 원의 지름처럼 놓아 보자. 원의 지름 위에 있는 임의의 한 점 $M$을 생각하면, 그 점에서 원 위의 다른 점 $P$까지의 거리는 지름의 두 끝점 중 더 먼 끝점 $B$까지의 거리보다 길 수 없다. 조금 더 수학적으로 접근하면, 원 위의 점과의 거리를 나타내는 식을 이용해 가장 먼 점이 반드시 지름의 한쪽 끝점이라는 사실을 증명할 수 있다.

여기서는 $dist(X, P)$가 $M$을 경유하는 경우를 가정했다. $M$을 경유하지 않는 경우에는 원의 가장 긴 현이 지름이라는 성질에 따라, 해당 거리가 지름보다 짧다는 것이 자명하므로 별도로 고려할 필요가 없다. 또한, $P$가 그림과 반대편(아래편)에 존재해도 마찬가지다. 즉,

원 위의 모든 점 P에 대해 $dist(X, P) \leq dist(X, B)$를 만족한다.

따라서 임의의 한 점에서 가장 먼 점을 구하면, 그 점은 어떤 지름 경로의 한쪽 끝점이 된다. 이제 해당 끝점에서 다시 가장 먼 점을 구하면, 두 점 사이의 거리가 트리의 지름이 된다. 물론 여기서 다루는 거리는 유클리드 거리가 아니라 간선의 개수로 정의되는 이산적인 거리이므로, 앞선 설명은 엄밀한 증명이라기보다 직관에 가깝다. 다만 이를 통해 임의의 노드에서 가장 먼 노드를 선택하면, 그 노드는 결국 어떤 지름 경로의 끝점에 해당한다고 이해할 수 있다.

구현

가장 먼 점이 여러 개 존재할 수 있으므로 그래프 탐색 알고리즘은 BFS(Breadth-First Search) 알고리즘을 사용했다.

인접 리스트를 생성하고 임의의 노드(1번 노드)부터 가장 먼 노드 $u$를 구한다. 다시 노드 $u$로부터 가장 먼 노드 $v$를 구한다. $v$는 여러 개일 수 있다.

$u$로부터 검색했을 때, $v$가 여러 개 나와야만 지름이 여러 개 존재한다고 판단했는데, $u$로부터 검색했을 땐 하나만 존재하고, $v$로부터는 검색했을 땐 여러 개의 지름이 생길 수 있다는 것을 놓쳤다.

소스 코드

const solution = (n, edges) => {
    const graph = edges.reduce((acc, [ u, v ]) => {
        acc[u].push(v);
        acc[v].push(u);
        return acc;
    }, Array.from({ length: n + 1 }, () => []));

    const bfs = (start) => {
        const visited = Array(n + 1).fill(false);
        let queue = [];
        let dist = 0;

        visited[start] = true;
        queue = [ start ];

        while (true) {
            const next_queue = queue.flatMap(current =>
                graph[current].filter(next =>
                    visited[next] ? false : visited[next] = true
                )
            );

            if (next_queue.length === 0) {
                break;
            }

            dist++;
            queue = next_queue;
        }

        return [ dist, queue ];
    };

    const u = bfs(1)[1][0];
    const [ diameter, v ] = bfs(u);

    return 1 < v.length ? diameter
        : 1 < bfs(v[0])[1].length ? diameter
        : diameter - 1;
}