BOJ 1167

2020-10-17

위 문제는 백준 사이트의 알고리즘 1167문제에 관한 설명입니다.

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다.

먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터

V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다)

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데,

하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.

예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고,

정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다.

각 줄의 마지막에는 -1이 입력으로 주어진다.

주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

소스코드


package day1017;
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 Main {
    static int[] bfs(List<Edge>[] list, int start, int n) {
        boolean [] visit = new boolean[n+1];
        int [] distance = new int[n+1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visit[start] = true;
 
        while(!queue.isEmpty()) {
            int v = queue.poll();
            for(Edge e : list[v]) {
                int next = e.next;
                int cost = e.w;
                if(!visit[next]) {
                    visit[next] = true;
                    queue.add(next);
                    distance[next] = distance[v]+cost;
                }
            }
        }
        return distance;
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Edge> [] list = (List<Edge>[])new ArrayList[n+1];
        int[] distance = new int[n+1];
        for(int i=0; i<=n; i++)
            list[i] = new ArrayList<>();
 
        for(int i=0; i<n; i++) {
            int from = scanner.nextInt();
            while(true) {
                int to = scanner.nextInt();
                if(to==-1)
                    break;
                int w = scanner.nextInt();
                list[from].add(new Edge(to, w));
            }
        }
        
        distance = bfs(list, 1, n); 
        int start = 1;
        for(int i=2; i<=n; i++)
            if(distance[start]<distance[i])
                start = i;
        
        distance = bfs(list, start, n); 
        Arrays.sort(distance);
        System.out.println(distance[n]);
    }
}
class Edge {
    int next;
    int w;
 
    public Edge(int next, int w) {
        this.next = next ;
        this.w = w;
    }
}

이번문제는 bfs로 풀었습니다.

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

트리의 지름은

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

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

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

과정.

입력 받을 때

기준 정점을 하나 입력 받고

-1이 입력되기 전까지

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

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

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

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

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

트리의 지름