[백준] 17073 나무 위의 빗물

입력이 들어올 때, 연결된 간선이 레벨 순서대로 들어오지 않기 때문에 다 받고 트리를 그려봐야 구조를 알 수 있다!!

그래서 각각의 노드에 대해서 연결된 다른 노드 목록들을 리스트에 먼저 저장해준다. 이때 한쪽 방향이 아닌 양쪽으로 연결된 관계를 모두 저장해준다.

그 다음 트리의 최상위 root가 되는 1번 노드를 queue에 넣고 1번 노드에 연결된 나머지 노드들을 다음 차례에 확인하기 위해 queue에 넣어준다. 그리고 이 과정을 queue가 빌 때까지 반복한다. 여기서 check 배열을 통해 이전에 해당 노드를 탐색했는지 확인하고 이미 탐색을 한 경우는 현재 cur 노드와 연결되어 있더라도 더 높은 레벨의 노드이므로 queue에 넣지 않아준다(해당 노드는 더이상 탐색하지 않는다)!!

이렇게 bfs로 쭉 들어가다 보면 아예 cur 노드 탐색 시 다음으로 탐색할 노드를 넣지 않는 경우가 생긴다! 이 경우가 바로 leaf 노드인 것이다!!

leaf 노드를 갑자기 왜 구하남? 부모 노드에 차있던 물이 1씩 내려오고 자식들에게 랜덤으로 간다고 해도, 어짜피 물이 더 이상 안움직이는 경우는 물이 맨 마지막 노드로 내려와서 고여 있는 경우다! 따라서 각 노드에 있는 물의 평균을 구하는 것이므로 결국 답은(전체물의양)/(leaf노드의수) 가 된다!

 

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
bool check[500001];
queue<int> q;
vector<int> v[500001];
int n, w;
int n1, n2, leaf_cnt = 0;
int main()
{
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d", &n1, &n2);
        v[n1].push_back(n2);
        v[n2].push_back(n1);
    }
    q.push(1);
    check[1] = true;
    while (!q.empty())
    {
        int flag = 0;
        int cur = q.front();
        q.pop();
        for (int i = 0; i < v[cur].size(); i++)
        {
            if (!check[v[cur][i]])
            {
                check[v[cur][i]] = true;
                q.push(v[cur][i]);
                flag = 1;
            }
        }
        if (!flag)
            leaf_cnt++;
    }
    printf("%lf", (double)w / (double)leaf_cnt);
    return 0;
}

 

Uploaded by Notion2Tistory v1.1.0