[BOJ_17073] 나무 위에 빗물

설명

---

조건을 잘 보면 리프노드에서 빗물이 고여있고 이때, 루트로 부터 시작한 이 빗물이 각 리프노드까지 갔을때의 평균치를 구하면된다. 예시 20/3 = 6.6666666667 이런식으로 구현하면 된다. 재귀적으로 깊이 우선 탐색으로 구현하고 이때의 값을 구해준다. 참고 할 점은 int로 리턴해줘야 시간초과가 나지 않는다. double return시 시간초과가 난다.

 

 

코드

---

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

public class Main {
    static List<Integer>[] tree;
    static boolean visited[];
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");

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

        tree = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N + 1; i++){
            tree[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < N - 1; i++){
            tk = new StringTokenizer(in.readLine(), " ");
            int U = Integer.parseInt(tk.nextToken());
            int V = Integer.parseInt(tk.nextToken());
            tree[U].add(V);
            tree[V].add(U);
        }
        System.out.println(((double)W/dfs(1)));
    }

    private static int dfs(int start) {
        int cnt = 0;
        visited[start] = true;
        for (int i = 0; i < tree[start].size(); i++) {
            if (!visited[tree[start].get(i)]) {
                visited[tree[start].get(i)] = true;
                cnt += dfs(tree[start].get(i));
            }
        }
        if(cnt == 0){
            return 1;
        }else{
            return cnt;
        }
    }
}

17073번: 나무 위의 빗물