[백준 17073] 나무 위의 빗물 (C++)

문제 링크: https://www.acmicpc.net/problem/17073

17073번: 나무 위의 빗물

1. 주의할 점

- 출력값에 소숫점 이하수가 10개 있으므로 cout.precision(11)을 통해 출력 형태를 맞춰준다.

- Vector를 통해 해당 Node와 연결되어 있는 Node를 저장한다(Node가 50만개여도 메모리초과가 나지 않으니까 안심하자)

 

2. 구현

- 문제를 요약하면, 입력받는 W를 Tree의 Leaf 수만큼 나눠주면 된다.

- BFS를 통해 접근하며, 시작은 Node 1, Visit[1]=true 로 설정을 한다.

- 이후 해당 Node에 연결되어 있는 다른 Node에 대해 Visit의 값이 False면 True로 바꿔준 후 추가

- 더 이상 추가할 Node가 없는 경우(이미 연결되어 있는 모든 Node들은 Visit값이 True일 때), Leaf로 판단한다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[500001];
bool visit[500001] = { false, };
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cout.precision(11);
	int num, a, b, cnt = 0;
	double sum;
	cin >> num >> sum;
	for (int i = 0; i < num - 1; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	queue<int> q;
	visit[1] = true;
	q.push(1);
	while (!q.empty()) {
		int cidx = q.front();
		q.pop();
		bool avail = false;
		for (int i = 0; i < v[cidx].size(); i++) {
			int next = v[cidx][i];
			if (visit[next]) continue;
			visit[next] = true;
			q.push(next);
			avail = true;
		}
		if (!avail)	cnt++;
	}
	cout << sum / cnt;
	system("pause");
	return 0;
}