[BOJ][Python] 백준 1033 번: 칵테일

1일 1PS 70일차!

📚 문제

---

골드 2 칵테일

💡 풀이 과정

---

• N-1 개의 비율이 주어지고 전체의 비율을 알아낸다.

  5

  4 0 1 1

  4 1 3 1

  4 2 5 1

  4 3 7 1

  입력에 대해서

  [a, b, c, d, e]

  1 * e = 1 * a

  1 * e = 3 * b

  1 * e = 5 * c

  1 * e = 7 * d

5개의 방정식을 통해 a+b+c+d+e 가 정수가 되는 가장 작은 값을 찾는 문제이다.

• 해당 문제는 N - 1 개의 간선으로 N 개의 노드가 연결되는 그래프로 볼 수 있다.
• 따라서 0 번을 기준으로 그래프를 생성하고, 그래프에 직접 연결될 수 있는 간선들을 확인한다.
• 해당 간선에서 그래프의 노드와 새로운 노드가 q : p 의 정수 비율을 가지면서 최소 정수이기 위해서 math.lcm(rate[a], p) 를 기준으로 삼는다.
  • math.lcm(rate[a], p) : math.lcm(rate[a], p) * q // p 로 비율을 맞춘다.
  • 그래프 노드쪽이 math.lcm(rate[a], p) 가 곱해졌기에 그래프 전체에 기존 비율을 맞추기 위해 math.lcm(rate[a], p) 를 곱해준다.
• 이후 해당 간선도 그래프에 추가한다.

📌포인트

---

• (0, 4), (1, 2), (3, 4) …
  • 해당 순서대로 간선이 입력되었다면 (1, 2) 는 그래프와 직접 연결되지 않는다.
  • 따라서 정렬 방법을 다시 생각하기보다는 N 의 최대가 10이므로 queue 의 가장 뒷부분으로 보내줬다.

💻 코드

---

import math
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

ingredients = deque()
rate = [0] * N

# 0 번 재료를 기준으로 설정한다.
rate[0] = 1
graph = {}

# a < b 이도록 설정
for _ in range(N - 1):
    a, b, p, q = map(int, input().split())
    if a > b:
        ingredients.append([b, a, q, p])
    else:
        ingredients.append([a, b, p, q])

# 오름차순 순서대로 정렬
# 0 과 연결된 것부터 시작해서 항상 연결된 재료들만 나온다.
sorted(ingredients, key=lambda x: (x[0], x[1]))

while ingredients:
    a, b, p, q = ingredients.popleft()

    # 만약 연결될 요소가 없으면 queue 의 가장 뒤로 보낸다.
    if rate[a] == 0 and rate[b] == 0:
        ingredients.append([a, b, p, q])
        continue
        
    # a 가 이미 연결된 재료가 되도록 변경한다.
    if rate[a] == 0:
        a, b = b, a
        p, q = q, p

    # p, q 의 비율을 서로소로 만든다.
    r = math.gcd(p, q)
    p //= r
    q //= r

    # 배수라면 그대로 적용
    if rate[a] % p == 0:
        rate[b] = (rate[a] // p) * q
    # 배수가 아니라면 a 가 (a, p) 의 최소 공배수가 되도록 만들어야한다.
    # 그리고 곱한 수 c 를 a 와 연결된 모든 숫자들에 곱해주어야한다.
    else:
        # a 와 관련된 수들에 곱해야할 수.
        c = math.lcm(rate[a], p) // rate[a]
        rate[a] *= c
        rate[b] = rate[a] * q // p

        # dfs
        visited = [False] * N
        visited[a] = True
        stack = []
        stack.append(a)
        while stack:
            node = stack.pop()
            if node not in graph:
                continue
            for next_node in graph[node]:
                if visited[next_node]:
                    continue
                stack.append(next_node)
                visited[next_node] = True
                rate[next_node] *= c

    #작성이 끝나면 graph 에 추가
    if a not in graph:
        graph[a] = []
    if b not in graph:
        graph[b] = []

    graph[a].append(b)
    graph[b].append(a)

print(*rate,sep=" ")