[백준] 1167 트리의 지름

www.acmicpc.net/problem/1167

1167번: 트리의 지름

2020-11-22

---

javjajimport java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
class Node {
    int n;
    int w;
    
    Node(int n, int w){
        this.n = n;
        this.w = w;
    }
}
 
public class Main1167 {
    public static int N, answer, leaf;
    public static boolean vtd[];
    public static List<Node> list[];
    
    public static void solve(int idx, int sum) {
        vtd[idx] = true;
        
        if(sum > answer) {
            answer = Math.max(sum, answer);
            leaf = idx;
        }
        
        for(Node node: list[idx]) {
            if(!vtd[node.n]) {
                solve(node.n, sum+node.w);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        list = new ArrayList[N];
        vtd = new boolean[N];
        for(int i = 0; i < N; i++) list[i] = new ArrayList();
        
        for(int i = 0; i < N; i++) {
            int p = sc.nextInt()-1;
            while(true) {
                int x = sc.nextInt()-1;
                if(x == -2) break;
                int w = sc.nextInt();
                list[p].add(new Node(x, w));
            }
        }
        
        //dfs (1)
        answer = 0;
        leaf = 0;
        solve(0, 0);
        //dfs (2)
        answer = 0;
        for(int i = 0; i < N; i++) vtd[i] = false;
        solve(leaf, 0);
        System.out.println(answer);
    }
}
 

 

'트리의 지름' 이라는 개념이 잘 이해가 안되서 고민고민하다가 결국 검색해서 찾아봤다. 내가 이해한 바로는 임의의 두 점 사이의 거리가 가장 멀려면, 어떠한 임의의 정점에서 다른 정점까지 갈 때의 가중치의 합이 가장 커야한다. 이 때, 이 문제에서는 루트를 알 수가 없으니, 임의의 정점을 찾고 나서 다른 정점까지 계산을 해야만 한다.

 

 

1. 편의상 정점은 0부터 시작하게 하였다. 입력값을 받을 때, 부모 정점 기준으로 새로운 정점을 저장할 때 자식 정점과 가중치값을 저장하였다.

 

2. dfs는 두 번을 돌았다. 첫 번째 dfs에서 돌 때는 leaf 노드를 가장 깊숙히 있는 leaf 노드를 찾았다. 어떠한 정점을 시작점으로 잡아도 상관은 없지만, 편의상 0으로 시작하였다. 정점들을 탐색하면서 가중치의 합이 가장 크게 나올 때의 idx값을 leaf라는 변수에 저장하였다.

 

3. 두 번째 dfs를 돌 때는 (2)번에서 저장해뒀던 leaf라는 변수를 시작점으로 잡고, 탐색을 시작했다. (2)번과 마찬가지의 방법으로 탐색하면서 가장 가중치가 큰 값을 더했었다.

 

 

(+) 두 번째 dfs를 돌 때 가중치의 합이 자꾸 이상하게 나왔었다. 왜 그러지 정말 한참을 고민하다가 코드를 다시 뜯어봤는데, sum + node.w가 아니라 sum+=node.w 로 되어 있어서 그랬었다.....;

solve(node.n, sum+node.w);