백준(BOJ) 1167 : 트리의 지름 (JAVA)

문제링크 : https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

트리의 지름을 구하는 문제다. 트리의 지름이란, 트리에서 가장 멀리 떨어져있는 두 노드 사이의 길이를 말한다.

 

트리의 지름을 구하는 방법은, 임의의 노드 x에서 DFS 백트래킹을 통해 가장 멀리 떨어져있는 노드 y를 구한 후, y에서 다시 DFS 백트래킹을 통해 가장 멀리 떨어져있는 노드 z를 구하면, y에서 z사이의 거리가 바로 트리의 지름이 된다. 이에 대한 증명을 해보자 -> (업데이트 예정)

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    private static int max = 0;
    private static int start = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int v = Integer.parseInt(br.readLine());
        
        @SuppressWarnings("unchecked")
        List<Link>[] lists = new ArrayList[v + 1];
        
        for(int i = 1; i <= v; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            lists[n] = new ArrayList<Link>();
            
            while(true) {
                int m = Integer.parseInt(st.nextToken());
                
                if(m == -1) break;
                
                lists[n].add(new Link(m, Integer.parseInt(st.nextToken())));
            }
        }
                
        boolean[] visited = new boolean[v + 1];
        dfs(lists, visited, 1, 0);
        
        visited = new boolean[v + 1];
        dfs(lists, visited, start, 0);
        
        System.out.println(max);
    } 
    
    private static void dfs(List<Link>[] lists, boolean[] visited, int i, int length) {
        visited[i] = true;
        
        if(length > max) {
            max = length;
            start = i;
        }
        
        for(Link next : lists[i]) {
            int m = next.getM();
            int distance = next.getDistance();
            
            if(!visited[m]) {
                dfs(lists, visited, m, length + distance);
                visited[m] = false;
            }
        }
    }
 
    private static class Link {
        private int m;
        private int distance;
        
        public Link(int m, int distance) {
            this.m = m;
            this.distance = distance;
        }
 
        public int getM() {
            return m;
        }
 
        public int getDistance() {
            return distance;
        }    
    }
}