백준 - 칵테일 (1033)

let N = Int(readLine()!)!
var graph: [[Int]] = Array(repeating: [], count: N)
var visited = Array(repeating: false, count: N)
var weight = Array(repeating: 1, count: N)
var answer = ""

for _ in 0..<N-1 {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    let (a, b, p, q) = (input[0], input[1], input[2], input[3])
    
    // a, b에 붙어 있는 애들 질량 업데이트
    let aWeight = weight[a], bWeight = weight[b]
    dfs(a, bWeight * p)
    visited = Array(repeating: false, count: N)
    dfs(b, aWeight * q)
    visited = Array(repeating: false, count: N)
    
    // 그래프에 연결
    graph[a].append(b)
    graph[b].append(a)
}

// 최종 최대공약수 찾기
var gcd = weight[0]

for i in 1..<weight.count {
    let big = max(gcd, weight[i])
    let small = min(gcd, weight[i])
    gcd = findGcd(big, small)
}

weight.forEach{ answer += "\($0 / gcd) " }
print(answer)

func dfs(_ start: Int, _ value: Int) {
    visited[start] = true
    weight[start] = weight[start] * value
    for node in graph[start] {
        if !visited[node] {
            dfs(node, value)
        }
    }
}

func findGcd(_ a: Int, _ b: Int) -> Int {
    if a % b == 0 {
        return b
    }
    return findGcd(b, a % b)
}

N-1개의 재료쌍이 주어진다 → 각 재료간의 관계를 연결하면 트리가 된다.

1. 처음에는 모든 재료의 질량을 1로 설정한다.
2. 재료 쌍의 비율을 하나씩 받아서 a와 b의 질량을 업데이트한다.
   1. 질량을 자연수로 만들기 위해 a에는 b의 질량 * p , b에는 a의 질량 * q 를 곱한다.
   2. 이때 a와 b에 각각 연결된 재료들의 질량도 업데이트해주어야 한다. dfs를 사용해서 연결된 재료를 탐색하고 a, b에 곱한 값과 같은 값을 각각 곱해준다.
3. 질량을 모두 업데이트 한 후에 a와 b를 연결시킨다.
4. 마지막으로 이렇게 계산된 모든 재료의 질량들을 전체 질량의 최대공약수로 나누어서 최종 질량을 구한 후 출력한다.