이번에 풀어본 문제는
백준 17073번 나무 위의 빗물 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, W;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }

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

            list.get(fst).add(sec);
            list.get(sec).add(fst);
        }

        int leafCount = 0;
        for (int i = 2; i <= N; i++) {
            if (list.get(i).size() == 1) leafCount++;
        }

        double answer = (double)W / leafCount;
        System.out.print(answer);
    }
}

📝 풀이

부모 노드에서 물을 가지고 있다면, 자식 노드 중 하나에게 공평하게 분배하고, 자식 노드는 다음 반복에서 동일한 행동을 합니다.
위와 같은 반복을 마치고 물의 이동이 멈춘 시점에서, 물을 가진 노드들의 전체 물의 값의 평균을 구하는 문제입니다.
단순하게 생각해보면, 물이 불어나는게 아니기 때문에 물의 총량은 무조건 처음에 주어진 W일것이고, 이 반복을 마치면 모든 물은 리프노드에 남게 됩니다.
따라서, 노드의 모든 연결관계를 정의한 후, (W / 리프노드의 개수)를 해주면 해결할 수 있습니다.

📜 후기

처음엔 복잡하게 접근했으나, 손으로 예제를 따라가보니 좀 더 간편한 방법을 찾을 수 있었습니다. 예제를 보고 부모노드가 무조건 자식노드보다 작은 값이어야 하는 줄 알았는데, 아니더라구요..ㅠ 참고하십쇼!