[백준] 1167번 : 트리의 지름 - 자바(Java)

Problem 🔒

문제

https://www.acmicpc.net/problem/1167

 

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

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 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

11

트리의 조건 🌲

1. 트리는 모든 노드가 하나의 연결된 그래프를 이루어야 한다.
2. 트리는 계층형 자료구조이기 때문에, 사이클이 없는 그래프이다.
   • 사이클(Cycle) : 그래프에서 노드가 자신에게 다시 도달할 수 있는 경로를 말한다.
   • 예를 들어, 노드A → 노드B → 노드C → 노드A 와 같은 형태를 말한다.
3. 트리는 두 노드 간에 반드시 하나의 유일한 경로만 존재한다.

Approach ⭕

1. 트리의 지름 찾는 방법
   • 트리의 지름은 트리에서 가장 먼 두 노드 사이의 거리를 말한다.
   • 첫번째로, 임의의 노드에서 가장 먼 노드(노드 A)를 찾는다.
   • 이 때 찾은 노드 A가 트리의 지름에서 한쪽 끝점에 해당한다.
   • 두번째로, 노드 A에서 가장 먼 노드(노드 B)를 찾는다.
   • 노드 A에서 가장 먼 노드 B가 트리 지름의 다른 끝점에 해당한다.
   • 트리는 사이클이 없고, 두 노드 간에 유일한 경로가 존재하기 때문에, 항상 이 방법이 옳다고 할 수 있다.
2. 간선 정보 입력
   • 1번부터 N번 노드까지 간선을 입력 받는 반복문을 생성한다.
   • 간선의 개수를 모르니, while 문으로 반복문을 생성한다.
   • 연결된 노드 번호 v가 -1이면 while 문을 탈출한다.
   • 간선은 ArrayList에 int 배열에 {노드번호, 가중치} 형태로 저장한다.
3. 첫번째 DFS (트리의 지름 한 쪽 끝 점 찾기)
   • 임의의 노드(노드 1)에서 시작하여 방문하지 않은 노드를 탐색하며, 경로의 거리를 누적(sum)한다.
   • 현재의 누적 거리가 최대 거리(d)보다 크면, 최대 거리(d)를 갱신하고, 노드 번호(node1)를 저장한다.
4. 두번째 DFS (트리의 지름 다른 끝 점 찾기)
   • 첫번째 DFS로 찾은 트리의 지름 한 쪽 끝 점인 node1에서 다시 탐색하여, 가장 먼 노드까지의 거리를 구한다.

---

Solution 💡

import java.util.ArrayList;
import java.util.Scanner;

public class 트리의지름2 {
    static int N, node1=0, d=0;
    static boolean[] visit;
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt()+1;
        visit = new boolean[N];
        for(int i=0; i<N; i++){list.add(new ArrayList<>());}
        // 간선 정보 입력 받기
        for(int i=1; i<N; i++){
            int n = sc.nextInt();
            while(true){
                int v = sc.nextInt();
                if(v==-1) break;
                int s = sc.nextInt();
                list.get(n).add(new int[]{v,s});
            }
        }
        DFS(1,0);
        visit = new boolean[N];
        DFS(node1, 0);
        System.out.println(d);
    }

    public static void DFS(int node, int sum){
        if(d<sum){d=sum; node1=node;}
        visit[node] = true;
        for(int[] a :list.get(node)){
            if(!visit[a[0]]){
                DFS(a[0], sum+a[1]);
            }
        }
    }
}