[백준 1033번] 칵테일 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
from math import gcd

def cocktail():
  for d in depth:
    for now in d:
      for next in child[now]:
        p,q = ratio[next]
        if value[now]*q == value[next]*p:
          continue
        if value[now]%p:
          value[0] *= p//gcd(value[now],p)
          return True
        value[next] = value[now]//p*q

N = int(input())

graph = [[] for i in range(N)]
for i in range(N-1):
  a,b,p,q = map(int,input().split())
  g = gcd(p,q)
  p,q = p//g,q//g
  graph[a].append((b,p,q))
  graph[b].append((a,q,p))

child = [[] for i in range(N)]
ratio = [0]*N
value = [1]*N
depth = [[] for i in range(N)]

dq = deque([(0,0)])
while dq:
  now,d = dq.popleft()
  depth[d].append(now)
  for next,p,q in graph[now]:
    if child[next]:
      continue
    child[now].append(next)
    ratio[next] = (p,q)
    dq.append((next,d+1))
    
while cocktail():
  continue

print(*value)

 

엄청 쉬워보였는데 은근히 까다로웠던 문제.

일단 파이썬은 math.gcd라는 사기함수가 있어서 한결 더 쉽게 풀 수 있는 것 같다.

 

알고리즘을 요약하면,

1. 0번을 부모노드로 잡고 각 부모노드의 child를 저장하여 트리 구조를 만든다.

2. 0번 노드부터 트리의 층별로 순회하면서 현재 노드와 자식 노드의 비율이 p,q인지 확인한다.

3. 만약 p,q가 아닌경우, 현재 노드의 값이 p로 나누어 떨어지면 자식노드의 값은 현노드값/p*q로 갱신한다.

4. 만약 p로 나누어 떨어지지 않으면 현재 노드와 p의 최대공약수로 p를 나눈 값을 0번 노드에 곱하고 처음부터 다시 갱신한다.

5. 모든 갱신이 끝나면 결과값을 출력한다.

 

 

오늘의 교훈) 트리 구조는 유용하다.