[BOJ/백준] 30680 - 별자리 만들기

30680번: 별자리 만들기

---

DFS + PriorityQueue

---

---

• 제목

별자리 만들기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB 

---

• 문제

밤하늘에 무지갯빛 별이 하나 반짝이고 있다. 이 무지갯빛 별과 N개의 장식을 사용해서 별자리를 만들어 밤하늘을 예쁘게 꾸미려고 한다.

각 장식의 특징은 다음과 같다.

• 각 장식은 Ai개의 별과 (Ai-1)개의 실로 이루어진 트리다. 실은 서로 다른 두 별을 연결한다.
• 각 장식에는 정확히 1개의 붉은색 별이 있다. 그리고 붉은색 별을 루트 노드로 생각했을 때, 리프 노드에 해당하는 별들은전부 파란색이다. 나머지 별들은 전부 흰색이다.
• 각 별에는 번호가 적혀있다. 번호는 1이상 Ai이하의 정수이다. 붉은색 별의 번호는 항상 1번이며 별마다 서로 다른 번호가 적혀있다.

별자리를 만들기 전에 스타는 다음과 같은 용어들을 정의했다.

 

• 별자리에서 별을 하나 선택하고 무지갯빛 별부터 선택한 별까지 실을 따라 이동할 때, 거치는 실의 최소 갯수를 해당 별의 깊이라고 정의한다.
• 별자리의 모든 별의 깊이를 구해서 이 중 최댓값을 별자리의 길이로 정의한다.

스타는 장식을 한 개씩 받아 가며 별자리에 장식을 단다. 모든 장식은 받은 순서대로 다음 규칙을 지키면서 달아야 한다.

 

• 첫 번째 장식의 붉은색 별과 무지갯빛 별 사이를 실로 연결한다.
• i (i > 1)번째 장식의 붉은색 별과 i-1번째 장식까지 달아서 만든 별자리에서 아직 다른 장식과 연결되지 않은 깊이가 최소인 파란색 별 사이를 실로 연결한다. 이러한 별이 여러 개라면 아무거나 선택한다.

스타는 규칙을 지키면서 길이가 최소인 별자리를 만들고 싶어한다. 스타가 만들 수 있는 별자리의 최소 길이를 구해보자.

---

• 입력

첫째 줄에 장식의 개수 N이 정수로 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터는 N개의 장식에 대한 정보가 스타가 받는 순서대로 주어진다.

각 장식에 대해서 첫째 줄에는 별의 개수 Ai가 정수로 주어지고 둘째 줄부터 (Ai-1)개 줄에는 실로 연결된 두 별의 번호 v와 
w가 공백을 사이에 두고 주어진다. (2 ≤ Ai ≤ 100,000; 1 ≤ v, w ≤ Ai; v ≠ w)

장식을 구성하는 별의 총개수는 500,000개를 넘지 않는다.

---

• 출력

스타가 만들 수 있는 별자리의 길이의 최솟값을 출력한다.

---

예제 입력1	예제 출력1
3 4 1 2 1 3 3 4 6 1 2 1 3 2 4 3 5 3 6 6 1 2 1 3 1 4 2 5 4 6	6

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static ArrayList<Integer> leafDepth;
    static ArrayList<Integer>[] edge;
    static boolean[] visited;

    static void DFS(int curr, int depth) {
        int count = 0;
        for (int next : edge[curr]) {
            if(visited[next]) {
                count++;
                continue;
            }
            visited[next] = true;
            DFS(next, depth + 1);
        }

        if (edge[curr].size() == count) {
            leafDepth.add(depth);
        }
    }

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(0);

        for (int i = 0; i < N; i++) {
            int A = Integer.parseInt(br.readLine());

            leafDepth = new ArrayList<>();
            edge = new ArrayList[A + 1];
            visited = new boolean[A + 1];

            for (int j = 0; j <= A; j++) {
                edge[j] = new ArrayList<>();
            }

            for (int j = 0; j < A - 1; j++) {
                st = new StringTokenizer(br.readLine());
                int v = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                edge[v].add(w);
                edge[w].add(v);
            }

            visited[1] = true;
            DFS(1, 0);

            int rootDepth = pq.poll();
            for (int depth : leafDepth) {
                pq.add(rootDepth + depth + 1);
            }
        }
        while (true) {
            int answer = pq.poll();
            if (pq.isEmpty()) {
                System.out.println(answer);
                break;
            }
        }
    }
}