[C++] 백준/BOJ - 17073 : 나무 위의 빗물

---

문제 이해 단계

https://www.acmicpc.net/problem/17073

17073번: 나무 위의 빗물

N개의 노드와 고인 물의 양 W가 주어진다.

루트 노드는 항상 1번으로 고정이다.
모든 노드는 루트 노드인 1번 노드의 자식 노드이다.

1번 노드로부터 물이 떨어지는데, 떨어지는 규칙은 다음과 같다.

1. 물을 가지고 있을 경우, 자식 노드가 있다면 자식 노드 중 하나를 골라 물을 1 준다.
(자식 노드가 여러 개라면 동일한 확률로 하나를 선택한다.)

2. 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아둔다.

물이 흐르는 과정을 거쳐, 물이 더 이상 움직이지 않게 되었을 때,
i번 노드에 쌓인 물의 양 기댓값을 P(i) 가정한다.

그때, P(i)가 0보다 큰 노드에 대해서 Pi의 평균을 구하는 문제

 

---

문제 접근 단계

이 문제에서 구하라고 하는 것은 전체 기댓값의 평균이다.
여기서 중요한 것은 Pi가 0보다 큰 노드에 대해서 구하라는 것인데,

이 말은 Pi가 0일 수도 있다는 말이다.
즉, 기댓값이 0일 수도 있다는 소리이다.

일단 기댓값을 구하는 구하는 방법부터 살펴보자.

문제에서 제시한 그림

문제 조건에서 노드의 개수가 2개라면
각 노드에 떨어질 확률은 1/2이고, 3개라면 1/3이다.
즉, 개수에 따라 확률이 정해져 있다.

개수도 정해져 있고, 확률도 정해져 있으니 이것은 이산확률변수이다.
이산확률변수에서 기댓값은 평균과 같은 말이다.

결국 이 문제는 평균을 구하라는 말인데,
pi가 0을 제외한 평균, 즉 확률이 0이 될 것을 제외한 평균을 구하라는 말이다.

 

---

Pi가 0이 되는 경우

어떤 경우를 0이 되는 경우라고 할까? 
당연히 물이 0인 경우이다.

문제 조건에서 물을 지니고 있으면, 반드시 자식 노드에게 물을 주라고 했다.
즉, 물이 더 이상 움직이지 않는 시점에는 물이 하나도 없어야 한다.

그렇기 때문에 Pi가 0이 되는 경우는
자식 노드를 가지고 있는 노드 즉, 부모 노드인 경우이다.

반대로, 자식노드를 가지고 있지 않은 노드,
리프(leaf) 노드라면 물을 가지고 있다.

이 리프 노드 같은 경우엔 평균 계산에 사용해줘야 한다.
리프 노드는 단순히 그냥 끝에 있는 노드라고 생각해 주면 된다.

---

리프 노드 찾기

그럼 이제 중요한 것은 리프 노드 찾기이다.

우리에게 주어진 정보는 연결된 노드의 정보밖에 없다.
이를 이용해서 BFS를 통해 부모 자식 관계를 파악할 수 있다.

그래프 탐색을 할 때,
연결되어 있는 노드의 개수를 보고 판단할 수 있다.

리프 노드의 경우, 가장 끝에 있기 때문에 연결된 것은 부모 노드밖에 없다.
즉, 연결된 노드가 1개이다.

만약 리프 노드가 아닐 경우,
부모 노드를 제외한 다른 자식 노드를 가지기 때문에, 연결된 노드가 2개 이상이다.

BFS 탐색을 하다가 이미 방문했던 곳에 부딪혔을 때
자기 자신과 연결된 노드 개수를 판단한다.

만약 1개라면, 부딪힌 것이 부모노드이기 때문에
자기 자신은 리프노드라고 판단할 수 있다.

이런 식으로 문제를 풀어나갈 수 있다.
이제 문제 구현 단계로 넘어가 보자.

 

---

문제 구현 단계

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N,W; // 입력

vector<int> v[500001]; // 노드
int endNode = 0; // 리프 노드
bool visited[500001] = {false,}; // 방문 확인

// 관계 만들고 리프 노드 찾기
void makeTree(int sx){
    visited[sx] = 1; // 1번 노드 체크
    queue<int> q;
    q.push(sx);
    while(!q.empty()){
        int x= q.front();
        q.pop();
        for(int i = 0; i < v[x].size(); i++){
            int nx = v[x][i];
            // 이미 방문한 노드에 부딪혔을 때
            if(visited[nx]) {
                // 자기 자신과 연결된 노드가 하나 뿐이라면
                if(v[x].size() == 1) endNode++; // 리프 노드 + 1
                continue;
            }
            visited[nx] = true;
            q.push(nx);
        }
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> W;
    for(int i = 0; i < N-1; i++){
        int v1,v2;
        cin >> v1 >> v2;
        v[v1].push_back(v2);
        v[v2].push_back(v1);
    }
    
    visited[1] = true;
    makeTree(1);
    cout.precision(10); // 출력 형식을 맞춰주기 위한 것
    cout << W / (double)endNode; // 소숫점 정밀도를 위한 double
}

핵심적으로 봐야 할 것은 makeTree 함수이다.
여기서 리프 노드를 찾는다.

1번 노드부터 시작하여, 1번 노드와 연결된 노드를 큐에 넣는다.
해당 작동은 일반적인 BFS와 같다.

방문을 확인해 주며 BFS를 돌리다가, 이미 방문했던 곳에 부딪히면
그때 자신이 리프노드인지 아닌지 판단하기 위해, 연결된 노드의 개수를 판단한다.

makeTree 함수에서 봐야 할 핵심적인 코드는 여기까지다.

아래에 main함수 부분에서 봐야 할 것은
백준에 출력형식을 맞춰주기 위해
cout.precision(10)을 해서 소수점 10자리까지 출력해주게 한 것이다.

또한 정확한 소수점 출력을 위해 double형 자료형을 사용했다.

 

---

시행착오

문제가 어려워서 못 풀었다기 보단,
수학 지식이 부족해서 못 풀었다.

DFS로 복잡하게 계산하다가 시간초과를 맞고
그냥 공식을 찾아보니 그렇게 할 필요가 없다는 것을 깨달았다.

https://toss.me/howudong

howudong님에게 보내주세요