[백준] 4315 나무 위의 구슬

문제

• 트리 정점 위에 박스가 N개 놓여져 있고 전체 박스에는 N개의 구슬이 랜덤하게 들어있다. (박스에 구슬이 없을 수 있다.)
• 트리의 각 정점은 1~N까지 번호가 매겨져 있다.
• 서로 인접한 정점끼리는 구슬을 옮길 수 있고, 하나를 움직일 때 한 번 움직인 것으로 친다.
• 모든 박스에 들어있는 구슬의 개수를 1개로 만들려고 할 때 움직임 최소 횟수 구하기

 

• 1 <= N <= 10,000

 

풀이

• 각 노드가 구슬을 받을 수 있는 경로는 부모 노드 또는 자식 노드에게다.
• 트리는 자식노드를 여러개 가질 수 있지만 부모노드는 하나만 갖는다.
  -> 리프 노드에서부터 시작해서 1개의 구슬만 남겨두고 모두 부모 노드에게로 넘기기로 한다.
• A노드의 부모노드인 B도 구슬이 없다면, B의 부모노드 C에게 받아와야 한다. 
  그렇게 되면 C -> B -> A 이런 순서로 구슬이 이동되고, C -> B 순서로 구슬이 이동되어야 한다.
  따라서 A노드는 B에게서 구슬을 받았다고 치고, 움직임 cnt 개수를 하나 증가시킨 뒤에, B노드가 C에게 구슬을 하나 더 받아야 함을 -1 로 표시하도록 한다.

 

from collections import deque

while True :
    N = int(input())	    # 노드 개수
    if N == 0 : break
    parent = [0] * (N+1)    # 부모 노드
    in_degree = [0] * (N+1) # 자식 노드의 개수
    ball = [0] * (N+1)      # 구슬 개수
    # 그래프 입력
    for _ in range(N) :
        node_info = list(map(int, input().split()))
        ball[node_info[0]] = node_info[1]
        for i in range(3, 3+node_info[2]) :
            parent[node_info[i]] = node_info[0]
            in_degree[node_info[0]] += 1

    # 리프노드로부터 시작하기
    q = deque([])
    for i in range(1, N+1) :
        if in_degree[i] == 0 :
            q.append(i)
    
    cnt = 0
    while q :
        now = q.popleft()

        # 부모노드에게 구슬 옮기기
        ball[parent[now]] += ball[now]-1
        cnt += abs(ball[now] - 1)

        # 부모 노드의 차수 -1
        in_degree[parent[now]] -= 1
        if in_degree[parent[now]] == 0 :
            q.append(parent[now])


    print(cnt)

 

References

• 백준 오늘의 문제