[Algorithm] 프로그래머스 - 트리 트리오 중간값

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

접근

그래프 탐색 문제이므로 DFS나 BFS를 사용한다.

n의 범위가 $3\leq{…}\leq{250,000}$ 이므로 그래프 탐색에서 $O(1)$의 추가적인 탐색만 허용한다.

이 문제는 DFS로는 해결할 수 없다.

이 문제의 핵심은 말단 노드로부터 탐색(말단 노드가 루트 노드가 되어 탐색)했을 때,

새로운 말단 노드까지 이동한 거리만큼이 두 점 사이의 거리가 되는 데 있다.

또한, 이 문제의 특징은 f의 매개변수의 개수가 3개라는 것이다.

루트 노드로부터 깊이가 제일 큰 상위 3개 노드의 이동 거리만 알면 된다.

따라서, 깊이 우선 탐색(DFS)를 진행하면 깊이를 우선을 탐색해

루트 노드로부터 각 노드까지의 일관된 깊이를 알기 힘드므로, BFS를 사용하여 문제에 접근하는 게 좋다.

그럼 BFS를 한 번만 진행하면 되는 걸까?

아니다. 최초 탐색을 진행하는 노드는 문제 해결 측면에서 보면 무작위다.

(말단 노드 → 말단 노드)에 해당하는 BFS가 끝나야 비로소 문제의 답이 도출될 수 있다.

하지만, (말단 노드 → 말단 노드) 중에서도 어느 말단 노드에서는 답이 안 될 수도 있다.

예를 들어, 다음과 같은 상황이다.

4에서 최초로 BFS를 진행했다고 가정해보자.

그러면 가장 깊이가 길면서 말단 노드는 1, 2, 3, 8에 해당한다.

이 중에서 8을 제외한 1, 2, 3 중에 한 노드로부터 다시 BFS가 진행된다면,

$f(1, 7, 8)=3$이 되어 (말단 노드 → 말단 노드)를 만족하면서 답을 도출하지 못하는 경우가 된다.

따라서, BFS를 여기서 한 번 더 진행하여 총 세 번을 진행해야 문제를 해결할 수 있다.

또한, 총 세번의 BFS를 진행하는 동안 탐색이 완료되었을 때의 상위 3개 노드가 최대가 되는 거리를 보장하지는 못하므로,

각 BFS마다 상위 3개 노드에서의 중간값을 계산하여 최댓값을 구한다.

소스코드(Java)

import java.util.*;

class Pair {
    int first;
    int second;

    Pair(int first, int second) {
        this.first= first;
        this.second = second;
    }
}

class Solution {

    Map<Integer, List<Integer>> graph = new HashMap<>();
    Queue<Integer> levelQueue = new LinkedList<>();

    public int solution(int n, int[][] edges) {
        for(int i = 0; i < edges.length; i++) {

            List<Integer> to = graph.getOrDefault(edges[i][0], new ArrayList<Integer>());
            to.add(edges[i][1]);
            graph.put(edges[i][0], to);

            List<Integer> from = graph.getOrDefault(edges[i][1], new ArrayList<Integer>());
            from.add(edges[i][0]);
            graph.put(edges[i][1], from);
        }

        int max = -1;
        int start = edges[0][0];

        for(int i = 0; i < 3; i++) {

            start = bfs(start);

            Queue<Integer> tempQueue = new LinkedList<>(levelQueue);
            int[] levels = {tempQueue.poll(), tempQueue.poll(), tempQueue.poll()};
            Arrays.sort(levels);
            max = Math.max(max, levels[1]);
        }

        return max;
    }

    public int bfs(int start) {

        boolean[] visited = new boolean[250001];

        Queue<Pair> queue = new LinkedList<>();

        queue.offer(new Pair(start, 0));

        if(levelQueue.size() >= 3) levelQueue.poll();
        levelQueue.offer(0);

        visited[start] = true;

        int lastNode = -1;

        while(!queue.isEmpty()) {

            Pair pair = queue.poll();
            for(int node : graph.get(pair.first)) {

                if(!visited[node]) {

                    lastNode = node;

                    queue.offer(new Pair(node, pair.second+1));
                    visited[node] = true;

                    if(levelQueue.size() >= 3) levelQueue.poll();
                    levelQueue.offer(pair.second+1);
                }
            }
        }

        return lastNode;
    }
}