👩‍💻문제

백준 - 칵테일

예제 입력1

5
4 0 1 1
4 1 3 1
4 2 5 1
4 3 7 1

예제 출력1

105 35 21 15 105

예제 입력2

2
0 1 6 4

예제 출력2

3 2

예제 입력3

3
0 1 9 8
1 2 9 8

예제 출력3

81 72 64

예제 입력4

4
2 3 6 8
0 1 9 3
3 0 7 5

예제 출력4

60 20 63 84

🌟 풀이

이 문제는 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다.
DFS를 사용하여 유클리드 호제법으로 비율의 최소 공배수와 최대 공약수를 구하고, 재료의 최소 질량을 구하면 된다.

1. 그래프를 이용해 각 재료의 비율 자료를 그래프로 구현한다.

   graph
   [0] -> (4, 1, 1) 
   [1] -> (4, 1, 3) # 재료1 : 재료4 = 1: 3 
   [2] -> (4, 1, 5)
   [3] -> (4, 1, 7)
   [4] -> (0, 1, 1), (1, 3, 1), (2, 5, 1), (3, 7, 1)

2. 비율의 최소 공배수를 구한다.

   1:1 의 최소 공배수 1
   3:1 의 최소 공배수 3
   5:1 의 최소 공배수 5
   7:1 의 최소 공배수 7

   1,3,5,7의 최소 공배수 => 105 (lcm)

3. 임의의 시작점에 최소공배수를 저장한다.
   ingredient[0] = lcm (105)

4. dfs 탐색을 수행하면서 이전 노드의 값과의 비율을 계산하여 저장한다.
   0부터 시작하면 0 -> 4 -> 1 -> 2 ->3 순으로 실행한다.

   ingredient[4] = ingredient[0] * 1/1 = 105
   ingredient[1] = ingredient[4] * 1/3 = 35
   ingredient[2] = ingredient[4] * 1/5 = 21
   ingredient[3] = ingredient[4] * 1/7 = 15
   

   ingredient

   [0]	[1]	[2]	[3]	[4]
   105	35	21	15	105

5. 각 노드의 최대공약수로 약분해준다.
   105, 35, 21, 15의 최대 공약수는 1
   => 각 리스트의 값을 1로 나눠서 출력한다.
   => 105 35 21 15 105

코드

# 칵테일
# 1. DFS 사용
# 2. 첫 시작 노드의 최소공배수 구하기
# 3. 인접노드 * (비율)
# 4. 업데이트 된 리스트 최대 공약수로 약분

N = int(input())
graph = [[] for _ in range(N)]
visited = [False] * N
ingredient = [0] * N
lcm = 1


def gcd(a, b):  # 최대 공약수
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


for _ in range(N - 1):
    a, b, p, q = map(int, input().split())
    graph[a].append((b, p, q))
    graph[b].append((a, q, p))
    lcm = lcm * p * q // gcd(p, q)  # 최소공배수 # 2. 첫 시작 노드의 최소공배수 구하기

def dfs(start):  # 시작 노드, 최소공배수
    visited[start] = True

    for next in graph[start]:
        if not visited[next[0]]:
            ingredient[next[0]] = ingredient[start] * next[2] // next[1] # 3. 인접노드 * (비율)
            dfs(next[0])


ingredient[0] = lcm
dfs(0)  # 1. DFS 사용

greatest = ingredient[0]
for ingred in ingredient:  # 최대공약수 구하기
    greatest = gcd(greatest, ingred)

for i in range(N): # 최대공약수로 약분 # 4. 업데이트 된 리스트 최대 공약수로 약분
    ingredient[i] = int(ingredient[i] // greatest)

for ingred in ingredient:
    print(ingred, end=" ")

정리하며

수학문제였다면 어떻게든 끼워맞춰서 풀었을 텐데... 막상 알고리즘을 생각하려 하니 모르겠어서 푸는 방법을 참고했다.
모든 비율의 최소 공배수를 구하고, dfs로 풀어야하는...
손으로 풀어보고 알고리즘을 정리하여 풀었다.
처음에 알고리즘 생각하는데에 30분.. 참고하고 손으로 풀고 코드로 표현하는데 30분.. 1시간 걸렸다.
앞으로도 알고리즘 생각 - 손으로 풀기 - 코드 표현 습관을 계속 길러야겠다.