BOJ - 나무 위의 빗물

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

---

Problem

---

Solve

문제를 이해하는데 조금 애먹긴했지만, 문제만 잘 이해하고 트리를 이해하고 있다면 쉽게 풀 수 있는 문제입니다.

루트노드에서부터 W의 물이 자식노드로 1씩 이동하는데, 동일한 확률로 이동하고 물이 더이상 움직이지 않는 상태가 되었을때 정점에 물이 있을 기댓값 Pi이 0이상인 곳의 평균을 구해야합니다.

물이 더이상 움직이지 않는 상태라는 것은 트리의 LeafNode를 뜻하며 Pi가 0이상인 곳의 평균이라는 것은 LeafNode에있는 물의 평균 값을 구하는 것입니다.

즉, W / LeafNode의 개수를 구하는 문제입니다.

N-1개의 간선을 통해 각 노드와 연결된 정점을 저장해줍니다. 간선이 정렬되어 주어지지 않기 때문에 인접리스트로 연결된 정점을 저장해줍니다.
그리고 LeafNode는 연결된 정점이 부모노드가 1개인 노드이기 때문에 각 노드에서 인접리스트의 크기가 1인 정점의 개수를 파악하면 됩니다.

O(N)으로 문제를 해결해줄 수 있게됩니다.

---

Code

import java.io.*;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;
public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());

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

		for(int i=0;i<N-1;i++){
			st = new StringTokenizer(br.readLine()," ");
			int U = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());

			tree.get(U).add(V);
			tree.get(V).add(U);
		}

		int count = 0;
		for(int i=2;i<tree.size();i++){
			List<Integer> link = tree.get(i);
            //인접 정점이 1개인 경우 leaf node
			if(link.size() == 1) count++;
		}

		bw.write(String.format("%.03f",(double)W/count));
		bw.flush();
		bw.close();
	}
}

---

Result

---

Reference

https://www.acmicpc.net/board/view/37116