백준 17073 : 나무 위의 빗물

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

17073번: 나무 위의 빗물

 

문제에서 노드 별 물 양의 기대치를 더하라고 해서 왠지 복잡할 것 같지만 결국 모든 물이 리프 노드로 떨어지기 때문에 사실 리프 노드의 갯수만 구하면 되는 문제다.

 

단 주의해야 할 점은, "정답과의 차이가 10^-3 이하인 값은 모두 정답으로 인정된다." 이 부분이다.

c++의 cout.precision(n)의 경우 소수점 아래 n자리까지 출력 가능하다고 알고있었는데, 그건 fixed와 함께 썼을 때고, fixed를 쓰지 않을 시 정수부를 포함해서 n개의 수를 출력한다.

 

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

using namespace std;

int n, total_water, leaf_cnt;
vector<int> edge[500'001];
bool visited[500'001];

//리프 노드의 갯수 구하기
void bfs() {
	int cur, num_edge, next;
	queue<int> q;
	q.push(1);
	visited[1] = 1;

	while (!q.empty()) {
		cur = q.front();
		q.pop();

		num_edge = edge[cur].size();
		if (cur == 1) num_edge++;
		
		if (num_edge == 1) {
			leaf_cnt++;
			continue;
		}

		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			if (visited[next]) continue;
			q.push(next);
			visited[next] = 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int node1, node2;
    
	cin >> n >> total_water;
	for (int i = 0; i < n - 1; i++) {
		cin >> node1 >> node2;
        //양방향 간선이므로
		edge[node1].push_back(node2);
		edge[node2].push_back(node1);
	}
    
	bfs();
    
	cout.precision(6);
	cout << fixed << (double)total_water / leaf_cnt;
	return 0;
}

메모리: 34044 kb

시간: 300 ms