트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// BFS 버전
public class Main {
    static int N; // 정점 개수
    static boolean[] visited; // 방문여부
    static ArrayList<int[]>[] A;
    static int farestNode; // 가장 먼 거리에 있는 노드번호
    static int maxDistance; // 가장 먼 거리
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 트리 정점의 개수
        A = new ArrayList[N+1];
        visited = new boolean[N+1];

        // 인접노드 리스트 만들어주기
        for(int i=1; i<N+1; i++){
            A[i] = new ArrayList<>();
        }

        // 연결된 인접노드 리스트 값 넣어주기
        for(int i=1; i<N+1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken()); // 1번째 토큰 : 현재노드

            while (st.hasMoreTokens()){
                int nextNode = Integer.parseInt(st.nextToken());

                // -1 만나자마자 while 루프 종료
                if (nextNode == -1) break;

                int distance = Integer.parseInt(st.nextToken());
                A[node].add(new int[] {nextNode, distance});
            }
        }

        // 가장 먼 노드 찾기
        BFS(1,0); // 1번 노드에서 시작
        visited = new boolean[N+1]; // 방문배열 초기화
        maxDistance = 0; // 최대 거리 초기화
        BFS(farestNode, 0);
        System.out.println(maxDistance);

    }
    static void BFS(int node, int distance){
        visited[node] = true; // 방문체크

        // 거리 비교 후 새로운 거리값이 더 크다면 farestNode, maxDistance 업데이트
        if(distance > maxDistance){
            maxDistance = distance;
            farestNode = node;
        }
        queue.add(node);

        while (!queue.isEmpty()){
            int nextNode = queue.poll();

            // 인접노드 리스트 순회
            for(int[] next : A[nextNode]){
                int nodeNum = next[0];
                int nodeDistance = next[1];

                if(!visited[nodeNum]){
                    BFS(nodeNum, distance + nodeDistance);
                }
            }

            // for문 다 돌때까지 더 이상 탐색할 다음 노드가 없다면 백트래킹
            visited[node] = false;
        }

    }
}

트리 지름

트리의 지름은 임의의 두 노드 사이가 가장 긴 경로이다.
트리 내의 가장 먼 두 노드가 어떤 노드들인지 알지 못한다는 것이다.
그래서 단순히 N번 노드가 가진 인접 노드 중에서 가장 긴 거리를 더하는 것으로는 트리의 지름을 정확히 구할 수 없다.

두 번의 BFS 가 필요하다

트리에서는 어떤 두 노드가 가장 멀리 떨어져 있을지 예측할 수 없다.
그래서 임의의 노드에서 가장 먼 노드를 찾고, 그 노드에서 다시 가장 먼 노드를 찾는 방식이 필요하다.
트리에서 가장 먼 두 노드는 일반적으로 서로 다른 부분에 위치하므로, 어디서 시작하느냐에 따라 가장 먼 노드가 다를 수 있다.
첫 번째 BFS에서 임의의 노드(1번) 에서 가장 먼 노드를 찾는다.
두 번째 BFS 에서 첫번 째 BFS에서 찾은 가장 먼 노드에서 다시 가장 먼 노드를 찾고, 그 거리가 트리의 지름이 된다.