백준 1167 트리의지름 Java

정답률 36퍼센트의 트리 문제이다. 

트리의 지름을 구하는 문제인데

트리에 존재하는 모든 경로 중 가장 긴 것의 길이를 트리의 지름이라고 한다.

 

BFS/DFS는 그래프에서만 해당되는 탐색 방법인 줄 알았는데

트리에서도 많이 사용되는 것을 알게 되었다.

트리의 부모를 찾을 때도 BFS탐색을 통해 구할 수 있고

트리의 지름도 BFS탐색을 통해 구할 수 있다.

 

트리의 지름을 구하는 방법은 따로 있는 것 같다.

1. 가장 긴 길이를 갖고있는 정점을 구한다.

2. 가장 긴 길이의 정점을 기준으로 다시 거리를 측정한다.

3. 거리를 저장한 배열 중 최대값이 트리의 지름이다.

 

입력 받을 때

기준 정점을 하나 입력 받고

-1이 입력되기 전까지

정점, 길이를 입력 받는다.

 

트리를 저장할 배열에 정점과 길이 -> 값이 2개 들어가야 하기 때문에 

한개의 클래스(Edge)를 더 만들고 List<Edge>[] 로 저장 한다.

 

그후엔 앞서 말했듯이 BFS를 통해 가장 긴 길이를 가진 정점을 찾고

그 정점을 기준으로 최대값을 찾는다.

트리의 지름을 찾는 방법을 기억하자.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
public class Q1167 {
    static int[] bfs(List<Edge>[] list, int start, int n) {
        boolean [] b = new boolean[n+1];
        int [] dist = new int[n+1];
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        b[start] = true;
 
        while(!q.isEmpty()) {
            int v = q.poll();
            for(Edge e : list[v]) {
                int y = e.y;
                int cost = e.cost;
                if(!b[y]) {
                    b[y] = true;
                    q.add(y);
                    dist[y] = dist[v]+cost;
                }
            }
        }
 
        return dist;
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        List<Edge> [] list = (List<Edge>[])new ArrayList[n+1];
        int[] dist = new int[n+1];
        for(int i=0; i<=n; i++)
            list[i] = new ArrayList<>();
 
        for(int i=0; i<n; i++) {
            int x = scan.nextInt();
            while(true) {
                int y = scan.nextInt();
                if(y==-1)
                    break;
                int cost = scan.nextInt();
                list[x].add(new Edge(y, cost));
            }
        }
        
        dist = bfs(list, 1, n); //가장 긴 길이의 정점 찾기
        int start = 1;
        for(int i=2; i<=n; i++)
            if(dist[start]<dist[i])
                start = i;
        
        dist = bfs(list, start, n); //가장 긴 길이의 정점을 루트로 dist배열 초기화
        Arrays.sort(dist);
        System.out.println(dist[n]);//정렬 후 최대값 출력
    }
}
class Edge {
    int y;
    int cost;
 
    public Edge(int y, int cost) {
        this.y = y ;
        this.cost = cost;
    }
}