[백준]1167: 트리의 지름 - JAVA

[백준]1167: 트리의 지름

www.acmicpc.net/problem/1167

1167번: 트리의 지름

풀이

🪑 트리에서 가장 먼 정점 사이의 거리를 구하는 문제이다. 정점의 위치 보다는 정점과 정점 사이의 cost값이 중요하다. 

다익스트라를 사용해서 정점을 순환하며 각 정점에서 최장거리를 구하고 그 거리중의 최대값을 구해도 답은 나오겠지만 이 문제는 그렇게 풀면 시간초과가 발생한다. 다른 방법을 생각해야 한다.

 

예제 입력을 보면서 생각을 해보쟝. 예제 입력을 트리로 변환해주면 다음과 같다.

 

각 정점에서 제일 먼 정점 까지의 거리를 구해보면 오른쪽에 적힌 값과 같다.

이때 트리에서 가장 먼 정점 사이의 거리는 1 <-> 5 인 11이다.

 

그림을 보면 공통점이 보인다. 5 -> 1, 1 -> 5가 가장 먼 정점 사이의 거리일때 모든 정점에서 부터의 최장 정점은 1 또는 5를 항상 포함하고 있다.

 

 

 

트리의 특성을 생각해 보면 모든 정점은 사이클이 없이 연결이 되어 있고, 한 정점에서 다른 정점으로 가는 경로는 유일하다. 그래서 가장 멀리있는 두 정점의 경로는 항상 유일하다.

 

또한 한 정점에서 가장 먼 정점으로 가는 경로와 가장 먼 정점 사이의 경로는 항상 일부가 겹친다. 아래 그래프를 보면서 이해해보자.

같은 그래프를 최장 거리를 가진 정점을 기준으로 표현하면 왼쪽과 같은 그림이 된다. 주황색으로 표시된 경로가 최장 경로가 된다.

 

이때 각 정점에서 제일 멀리있는 정점 까지 가는 길을 따라가 보면 항상 일부가 겹치는 것을 알 수 있다. 정점간 cost를 기준으로 경로를 결정하기 때문에 가장 긴 정점의 경로는 결국 어느 정점에서의 가장 먼 거리에 있는 정점의 경로와 겹칠 수밖에 없는 것이다. 

 

 

그렇기 때문에 모든 정점에서 부터의 최장 정점은 항상 가장 먼 정점인 1이나 5를 포함할 수 밖에 없다.

이에 대한 반례로, 만약 4에서 최장 정점이 2가 되려면 그 cost가 11보다 큰 값으로 변경되어야 한다. 이렇게 되면 가장 먼 정점 또한 2를 포함하도록 변경되는 것을 알 수 있다.

 

위에서 구했듯이 각 정점에서 최장 정점을 구하면 항상 가장 먼 정점 중 하나를 포함하는 것을 알 수 있다. 그럼 이제 그 정점에서 가장 먼 정점을 구하면된다. 1이 구해졌다면 1에서 가장 먼 정점인 5가 될 것이고, 5가 구해졌다면 가장 먼 정점인 1이 될 것이다.

즉, 다음과 같은 과정이 필요하다.

1. dfs를 통해 임의의 정점 하나에서 가장 먼 정점을 구한다. (임의의 정점은 아무거나 상관없다.)

2. dfs를 통해 구한 정점으로 부터 가장 먼 정점까지의 거리를 구한다.

 

dfs 2번으로 정답을 구할 수 있다. 시간 복잡도는 O(n)으로 매우 효율적이다.

 

코드

import java.util.*;
 
public class Main {    
 
    static ArrayList<Node>[] list;
    static boolean[] visited;
    static int max = 0;
    static int node;
    
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        list = new ArrayList[n + 1]; 
        for(int i = 1; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < n; i++) {
            int s = scan.nextInt();
            while(true) {
                int e = scan.nextInt();
                if(e == -1) break;
                int cost = scan.nextInt();
                list[s].add(new Node(e, cost));
            }
        }
        
        //임의의 노드(1)에서 부터 가장 먼 노드를 찾는다. 이때 찾은 노드를 node에 저장한다.
        visited = new boolean[n + 1];
        dfs(1, 0);
        
        //node에서 부터 가장 먼 노트까지의 거리를 구한다.
        visited = new boolean[n + 1];
        dfs(node, 0);
        
        System.out.println(max);
    }
    
    public static void dfs(int x, int len) {
        if(len > max) {
            max = len;
            node = x;
        }
        visited[x] = true;
        
        for(int i = 0; i < list[x].size(); i++) {
            Node n = list[x].get(i);
            if(visited[n.e] == false) {
                dfs(n.e, n.cost + len);
                visited[n.e] = true;
            }
        }
        
    }
    
    public static class Node {
        int e;
        int cost;
        
        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
    }
}