나무 위의 빗물
문제 해석
트리의 간선이 주어질 때, 각 정점에 쌓인 물의 양의 기댓값의 평균을 구하는 문제입니다.
W의 양의 물을 가지고 있고, 부모 정점에서 자식들에게 골고루 퍼뜨립니다. 자식 정점이 여러개면 동일한 확률로 그 중 하나를 골라서 퍼뜨립니다.
설계(20)
트리의 탐색 문제입니다.
우선 주어진 W를 각 자식들에게 퍼뜨리면 결국에 각 리프 노드에 어떠한 형태로 담기게 됩니다.
결국, W를 리프 노드의 개수로 나누면 되는 문제입니다.
저는, 트리의 특성을 이해하기 위해서 직접 트리로 이 문제를 풀었습니다.
우선 구조체를 이용하여 트리를 만듭니다.
각 트리에는 포인터 트리형 벡터가 저장되어있습니다.
트리 구조상, 자식의 개수가 몇개인지 한정되어있지 않았기 때문에 만든 자료형입니다.
주어진 간선으로 트리를 만든 후, 탐색하면서 자식이 없는 정점이 몇개인지 카운트하여 정답을 도출합니다.
구현(40)
코드
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
#define MAXN 500001
vector<int> adj[MAXN];
bool visited[MAXN];
int N,W;
double ans;
int cnt;
struct Tree{
vector<Tree*> child;
int num;
Tree (): num(0){}
~Tree (){
child.clear();
}
void make_tree(){
for (int i = 0 ;i < adj[num].size(); i++){
if (visited[adj[num][i]]) continue;
visited[adj[num][i]] = true;
Tree* tmp = new Tree();
tmp->num = adj[num][i];
child.push_back(tmp);
tmp->make_tree();
}
}
void find(){
if (child.size()==0) cnt++;
for (auto x: child){
x->find();
}
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> W;
for (int i = 0 ; i< N-1; i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
Tree tree;
tree.num = 1;
visited[1] = true;
tree.make_tree();
tree.find();
cout.precision(6);
cout << fixed << W/(double)cnt<<"\n";
return 0;
}
코드2(최적화)
사실 트리 자체를 구성할 필요가 없습니다.
리프 노드만 찾으면 되기 때문입니다.
각 간선 u,v를 방문처리하면서 방문을 한번만 하는 정점은 리프노드이기 때문에 해당 정점들만 카운트 하면 됩니다.
#include <iostream>
using namespace std;
#define MAXN 500001
int visited[MAXN];
int N,W;
int cnt;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> W;
int cnt = N;
for (int i = 0 ; i< N-1; i++){
int u,v;
cin >> u >> v;
if (visited[u] == 1) cnt--;
if (visited[v] == 1) cnt--;
visited[u]++;
visited[v]++;
}
if (visited[1]==1) cnt--;
cout.precision(6);
cout << fixed << W/(double)cnt<<"\n";
return 0;
}
디버깅
제출결과
트리 구조 특성상 역시나 아주 큰 메모리를 사용하였습니다.
트리 이용: 메모리 - 92288KB, 시간 - 452ms
코드2 최적화: 메모리 - 3936KB, 시간 - 128ms
마무리
단순 리프노드를 찾는 문제였습니다.
그렇지만, 트리를 굳이 구현해보면서 특성을 파악하도록 노력하였습니다.