백준/ Gold 5 문제 , 백준 파이썬 17073, 나무 위의 빗물 [트리]

백준/ Gold 5 문제 , 백준 파이썬 1068 , 나무 위의 빗물 [트리]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
node.js 로 DFS 풀이는 recursion error,  BFS 풀이는 메모리 초과로 계속 틀렸던 문제이다. 
문제 해답 자체는 리프노드만 찾으면 되는 건데, 계속 오류가나서 파이썬으로 풀었다.
똑같은 로직인데, 파이썬으로는 통과하고 자바스크립트로는 틀리는 문제.

 

 

 

 

문제 출처 🏠

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

17073번: 나무 위의 빗물

 

 

요구사항 📋

1번 정점에 저장되어있는 물을 자식노드로 일정한 비율로 나누어 전달.
물을 받은 자식노드에도 그 노드의 자식노드가 있다면, 똑같이 수행한다.
더이상, 물을 전달하지 않을때 물이 담긴 노드들의 평균값을 구하시오.

 

 

 

해결 전략 📝

트리의 간선들을 모두 이은 다음. 1번노드부터 BFS 진행.
이때 물을 1씩 나누지말고, 자식노드의 갯수만큼 나누어서 배분.
최종적으로 각 노드에 0이 아닌 값들의 갯수와 합을 계산하여 나누기.

 

 

 

기능 목록 📲

1. 트리의 간선을 이음. 이때, 양방향 그래프로 저장.  (누가 부모인지 간선만 보고 알 수 없음.)
2. 리프 노드의 개수를 구하는 함수. => cntLeafNodes

 

주의사항 ⚠️.

부모노드 숫자가 무조건 자식노드보다 크다는 보장 없음. => 리프노드 찾기

 

 

정답 💯

 

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

N,W=map(int,input().split())
Nodes=[[] for i in range(N+1)]
visited=[False for j in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    Nodes[a].append(b)
    Nodes[b].append(a)
    
def cntLeafNodes (node):
    global cnt
    visited[node]=True;
    if (len(Nodes[node])==1 & visited[Nodes[node][0]]):
        cnt+=1
        return
    for nextNode in Nodes[node]:
        if not visited[nextNode]:
            cntLeafNodes(nextNode)

cnt=0        
cntLeafNodes(1)
print(W/cnt)

 

느낀점 🧑‍💻

 

똑같은 풀이인데, 파이썬은 통과하고 자바스크립트는 런타임 에러가 나고... 이  과정속에서의 시간 소비가 너무 크다.