[백준 JAVA] 1033. 칵테일

문제 링크

---

https://www.acmicpc.net/problem/1033

접근 방법

---

비례식 여러 개를 합치는 문제입니다.

예를 들어 1) A : B = 2 : 3이고 2) A : C = 8 : 6이면 A : B : C = 4 : 6 : 3이 됩니다.

1)의 A와 C 값을 곱하면 12가 되고, 1) 에는 C가 없으므로 8이 됩니다.

곱한 결과값의 최대공약수는 4이므로 4로 나눠주면 3과 2가 됩니다.

1) 에다가 2를 곱해주고, 1)에 C가 없으므로 3을 넣어주면 4 : 6 : 3이 됩니다.

소스 코드

---

import java.util.*;
import java.io.*;

public class Main {

	static ArrayList<ArrayList<Integer>> arr;
	static int[] answer;
	static int n, visit;

	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}

	static void cocktail(int num, int mul) { // dfs
		answer[num] *= mul;
		visit |= (1 << num);
		
		for (int i : arr.get(num)) {
			if ((visit & (1 << i)) == 0) {
				visit |= (1 << i);
				cocktail(i, mul);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a, b, p, q, tmp1, tmp2, div;
		n = Integer.parseInt(br.readLine());
		answer = new int[n];
		arr = new ArrayList<>(n);

		for (int i = 0; i < n; i++) {
			answer[i] = 1;
			arr.add(new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			p = Integer.parseInt(st.nextToken());
			q = Integer.parseInt(st.nextToken());

			tmp1 = answer[b] * p;
			tmp2 = answer[a] * q;
			div = gcd(tmp1, tmp2);
			visit = 0;

			cocktail(a, tmp1 / div);
			cocktail(b, tmp2 / div);
			arr.get(a).add(b);
			arr.get(b).add(a);
		}

		for (int i = 0; i < n; i++) {
			System.out.print(answer[i] + " ");
		}
	}
}

코드 설명

---

입력받은 비율에서 얼마를 곱해야 전에 구한 비례식들과 합칠 수 있는지 계산합니다.
cocktail 메서드를 이용하여 연결된 노드의 비율 값을 재귀적으로 갱신합니다.

그 후에 각 인접리스트에 추가해 줍니다.