[백준 1167] 트리의 지름 / 자바 / 트리순회(dfs)

문제         

레벨: G2
알고리즘: DFS
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도   

• dfs를 통해 임의의 정점 하나에서 가장 먼 정점을 구한다. (임의의 정점은 아무거나 상관없다.)
• dfs를 통해 구한 정점으로 부터 가장 먼 정점까지의 거리를 구한다.

 

이게 가장 긴 지름임을 보장하는 이유는 예를 들어 설명하겠다.

1 - 2 - 3 - 4 - 5 - 6 이런 일직선의 트리를 생각해보자

가장 긴 지름을 구하려면 끝점 두 개를 구해야 한다. 

1. 임의점에서 dfs를 하면 끝점 하나가 찾아진다.

2. 그 끝점을 기준으로 dfs 하면 다른 끝점이 찾아진다.

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;
        }
    }
}