17073. 나무 위의 빗물

<첫번째 풀이>

- 자식 노드를 찾는 게 핵심인 문제였다.

- 모든 빗물은 부모에서 자식으로 떨어지고, 더이상 빗물이 움직이지 않을 경우 상황이 종료되므로 처음 주어진 빗물 W는 일정한 크기에서 변화하지 않게 되고, 결론은 최밑단의 "잎노드"를 찾는 문제였다.

- 처음에는 잎노드를 찾기 위해 우선 노드의 연결을 링크드 리스트를 통해 구했고, 방문여부를 통해 이미 방문한 노드를 구별하기 위해 -1의 값을 넣어주었고, 또 다른 연결된 노드에 해당되는 인덱스에는 값을 하나 올려주었다.

- 그 이유는 다음 자식노드에서 이미 방문한 노드를 체크해주기 위해 연결된 size에서 방문 노드를 제거하기 위한 개수를 알기 위해서였다.

- 말로 하면 어렵지만 코드를 보면 이해가 더 빠를 것이다.

package december.fifth;

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

public class B_17073_나무위의빗물 {

	static int count; // 마지막에 물이 남아있는 정점들 => 잎노드!!!!

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int[] check = new int[N]; // 방문여부(-1)와 리스트에서 제외될 수(양의정수)의 개수
		List<Integer>[] list = new ArrayList[N]; // 노드 연결 여부
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int U = Integer.parseInt(st.nextToken()) - 1;
			int V = Integer.parseInt(st.nextToken()) - 1;
			list[U].add(V);
			list[V].add(U);
		}
		solve(0, list, check);
		String result = String.format("%.10f", W / (count * 1.0));
		System.out.println(result);
	}

	private static void solve(int node, List<Integer>[] list, int[] check) {
		int size = list[node].size(); // 현재 연결된 노드
		int childNum = size - check[node]; // 자식 노드 개수 = 연결된 노드 - 이미 방문한 노드
		check[node] = -1; // 방문 체크
		if (childNum == 0) { // 자식 노드가 없으면 고인 물이 됨.
			count++;
		}
		for (int i = 0; i < size; i++) {
			int idx = list[node].get(i);
			if (check[idx] == -1) // 이미 방문한 노드
				continue;
			check[idx]++; // 이미 리스트에서 방문한 노드가 있음을 알려주기 위함.
			solve(idx, list, check); // 자식 노드 계산 이어가기
		}
	}
}

<두번째 풀이>

=> 근데!!! 잎노드를 구하는 방법은 더 쉬운 간단한 방법이 존재했다.

바로!!! 연결된 간선의 정보를 입력 받을 때 일차원 배열에 하나씩 증가시키고 간선의 정보가 1인, 즉 배열의 값이 1인 노드만을 구해주면 되었다!!!!!

자식이 아닌 부모는 항상 위에서 1개의 간선이 아래에 1개의 간선이 필수적으로 필요하므로 최소 2개 이상의 간선을 가지게 된다.

하지만!! 자식노드는 위에서 부모와 연결해주는 간선 1개만이 존재하게 되므로 간선의 개수가 1인 노드가 바로 자식노드가 되는 것이다.

 

** 입력 받을 때 일차원의 인덱스 값을 증가시키고 1의 값을 가진 정점의 수를 찾아 입력받은 W를 앞에서 구한 정점의 수로 나누어주면 되는 문제였던 것이다!

*** 루트 노드가 간선이 1일 경우가 있을 수 있으므로 루트를 제외한 노드에서 간선이 1인 노드를 찾아야 한다!!!

package december.fifth;

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

public class B_17073_나무위의빗물2 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int[] arr = new int[N]; // 간선의 개수
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int U = Integer.parseInt(st.nextToken()) - 1;
			int V = Integer.parseInt(st.nextToken()) - 1;
			arr[U]++;
			arr[V]++;
		}
		int count = 0; // 잎노드의 수
		for (int i = 1; i < N; i++) { // 주의!!! 루트 노드는 1일수도 있으므로 제외!!
			if (arr[i] == 1)
				count++;
		}
		String result = String.format("%.10f", W / (count * 1.0));
		System.out.println(result);
	}

}