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

🏅 Gold 5

✏️ 1차 솔루션

⭐️ priority_queue 사용

1. u, v 를 입력받을 때, 부모 노드를 구분할 수 없으므로 u 를 기준으로 오름차순 정렬하도록 우선순위 큐에 push ➡️ 일단 u 가 1인 경우가 먼저 오게 됨
2. u 가 1이거나 이미 방문한 노드이면 u 가 부모노드, 이외의 경우는 v 가 부모노드로 해서 tree vector 완성
3. 자식 노드가 없는 노드가 리프노드가 되므로 tree[n].size()==0 인 개수가 리프노드의 개수
4. cout.precision(11) 로 소수점 형식 맞춰주기

🚨 1차 trouble

출력은 정상적으로 되는데 자꾸 틀렸다함

✏️ 최종 솔루션

1. u 와 v 가 등장할 때마다 count 해서 vector 에 넣어줌
2. 리프노드라면 부모 노드와 연결될 때 딱 1번만 count 되므로 count 값이 1 ➡️ count 값이 1인 노드 개수 = 리프노드 개수
3. 소수점 형식 맞춰주기 위해 printf("%.10f", w / cnt) 사용 ➡️ 소수점 뒤로 10자리

🔗 [참고] 화면출력 자리수 표현 방법

📌 self feedback

루트노드가 무조건 고정적인 경우, 부모 노드와 자식 노드의 구분 없이 u, v 값으로 가져오는 경우는 노드가 등장하는 개수만 count 해줘도 리프노드 여부 판단할 수 있음

✏️ 최종 code

#include <iostream>
using namespace std;

int water[500001];
double cnt=0,w;
int n;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> w;
    
    for(int i=1;i<n;i++) {
        int u, v;
        cin >> u >> v;
        
        water[u]++;
        water[v]++;
    }
    
    for(int i=2;i<=n;i++) {
        if(water[i]==1) cnt++;
    }
    
    printf("%.10f", w / cnt);

}