[백준]17073번 나무 위의 빗물 - Java

문제

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

17073번: 나무 위의 빗물

 

 

풀이

처음엔 무슨 소린가 했는데 결국 리프 노드(자식이 없는 노드)의 수로 총 빗물의 양을 나눠주면 답이다!

그러므로 리프 노드를 어떻게 판별할지가 포인트인데,

트리에선 자신과 연결된 노드가 하나밖에 없는 경우가 리프 노드이다. (2개 이상이 연결되어 있으면 자식 노드가 존재하는 것이니까)

이 점을 이용하여 풀었다.

 

자세한건 주석으로!

 

 

코드

// 17073번 나무 위의 빗물
// https://www.acmicpc.net/problem/17073

package BAEKJOON;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Num17073_나무위의빗물 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        // 연결 리스트로 구현
        ArrayList<Integer>[] arrayLists = new ArrayList[N + 1];
        for (int i = 1; i < N + 1; i++) {
            arrayLists[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            // 연결되어 있는 노드라고 표시
            arrayLists[num1].add(num2);
            arrayLists[num2].add(num1);
        }

        int answer = 0;
        for (int i = 2; i < N + 1; i++) {
            if (arrayLists[i].size() == 1) { // 간선의 수가 1개면 리프 노드
                answer++;
            }
        }
        System.out.println(String.format("%.10f", (double) W / answer));
    }
}