칵테일

문제

august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다.

경근이는 인터넷 검색을 통해서 재료 쌍 N-1개의 비율을 알아냈고, 이 비율을 이용해서 칵테일에 들어가는 전체 재료의 비율을 알아낼 수 있다.

총 재료 쌍 N-1개의 비율이 입력으로 주어진다. 이때, 칵테일을 만드는데 필요한 각 재료의 양을 구하는 프로그램을 작성하시오. 이때, 필요한 재료의 질량을 모두 더한 값이 최소가 되어야 한다. 칵테일을 만드는 재료의 양은 정수이고, 총 질량은 0보다 커야한다.

비율은 "a b p q"와 같은 형식이고, a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다.

입력

첫째 줄에 august14를 만드는데 필요한 재료의 개수 N이 주어지며, N은 10보다 작거나 같은 자연수이다.

둘째 줄부터 N-1개의 줄에는 재료 쌍의 비율이 한 줄에 하나씩 주어지는데, 문제 설명에 나온 형식인 "a b p q"로 주어진다. 재료는 0번부터 N-1까지이며, a와 b는 모두 N-1보다 작거나 같은 음이 아닌 정수이다. p와 q는 9보다 작거나 같은 자연수이다.

출력

첫째 줄에 칵테일을 만드는데 필요한 각 재료의 질량을 0번 재료부터 순서대로 공백으로 구분해 출력한다.

예제 입력 1 복사

예제 출력 1 복사

105 35 21 15 105

풀이

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static ArrayList<ingredient>[] A;
    static long lcm; // 최소 공배수
    static boolean[] visited; // 방문배열
    static long[] ratio;

    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); // 재료개수
        A = new ArrayList[N]; // 재료를 인접리스트로 생각한다.
        visited = new boolean[N]; // 방문배열 초기화
        ratio = new long[N]; // 재료 비율 값
        lcm = 1; // 최소공배수 초기화

        for(int i=0; i<N; i++){
            A[i] = new ArrayList<ingredient>();
        }

        for(int i=0; i<N-1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            long p = Long.parseLong(st.nextToken());
            long q = Long.parseLong(st.nextToken());

            // 인접노드 리스트 값 서로 넣어주기 (다른 재료와 비율)
            A[node1].add(new ingredient(node2, p, q));
            A[node2].add(new ingredient(node1, q, p));

            // 입력값 최소공배수 구하기
            lcm *= (p * q) / gcd(p,q);
        }

        ratio[0] = lcm;
        DFS(0);

        long ratioGCD = ratio[0];

        // 전체 DFS 탐색 후 배열 값들의 최대공약수로 나눠줘야됨
        // 배열 값들의 최대공약수 구하기
        for(int i=1; i<N; i++){
            ratioGCD = gcd(ratioGCD, ratio[i]);
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<N; i++){
            bw.write(ratio[i]/ratioGCD + " ");
        }

        bw.flush();
        bw.close();

    }
    // 최대공약수 구하기
    private static long gcd(long A, long B){
        // 만약 B가 0으로 들어왔다면 최대공약수 구했으므로 return
        if(B == 0) return A;
        // 그게 아니라면 다시 나머지 연산
        return gcd(B, A%B);
    }

    // DFS 수행 (i번째 node DFS 수행)
    private static void DFS(int i){
        // 방문하지 않았다면 방문체크 후 인접리스트 dfs 수행
        visited[i] = true;

        for(ingredient next : A[i]){
            // 인접리스트 순회하면서 방문하지 않은 노드 있다면
            int b = next.getB();
            if(!visited[b]){
                // 비율계산해서 값 update 후 DFS 재귀 호출
                // 나눗셈 먼저하면 0이 나올 수 있으므로 곱셈먼저 수행
                ratio[b] = ratio[i] * next.getQ() / next.getP();
                DFS(b);
            }
        }
    }
}

// ingredient 클래스 정의
class ingredient{
    int b; // 다른 재료 번호
    long p; // 비율 p
    long q; // 비율 q

    public ingredient(int b, long p, long q){
        super();
        this.b = b;
        this.p = p;
        this.q = q;
    }

    public int getB(){
        return b;
    }

    public long getP() {
        return p;
    }

    public long getQ(){
        return q;
    }
}

구현하는게 레전더리 어려움;;
각 재료를 그래프라고 생각한다. -> 인접 리스트 구현
- 2번째 줄 ~ N-1번째 줄의 값을 받으면서 최대공약수를 구하여 lcm(최소공배수)에 곱해주면서 업데이트한다.
- 2번째줄 부터는 입력 값의 형태가 a b p q 라면
- a/b = p/q이다.
- 이러한 구조를 저장하기 위해 새로운 클래스를 정의한다.(class ingredient)
- 인접노드 리스트에 각각 서로의 인접노드 번호값, p, q(혹은 q, p)값을 넣어준다.
임의의 노드에서 DFS 문을 수행한다.
- 비율값을 저장하는 배열의 값은 모두 0으로 초기화 되어있으므로 계산해두었던 lcm을
- 시작하고자하는 임의의 노드번호에 저장해주고 해당 번호부터(0번) DFS를 수행한다.

DFS

방문 체크 후 해당 번호의 노드의 인접리스트 순회한다.
인접리스트를 순회하면서 방문하지 않은 노드를 발견한다면
- 해당 노드번호의 ratio배열 값을 계산 후 update 해준다
- a/b = p/q 이므로
- b = a * q / a 이다. 이 값을 ratio[b]값에 업데이트 해주면된다.
- 그리고 DFS(b)를 수행한다.

DFS를 모두 수행한 후

DFS를 모두 수행했다는 뜻은 모든 노드를 방문하고 ratio 배열값이 채워져있다는 뜻이다.
하지만 필요한 재료의질량은 모두 더한 값이 최소가 되어야 하므로, 즉 최소 공배수를 만족해야 한다는 뜻이다.
배열값의 최대공약수를 구해준 뒤, 배열의 값을 출력할때 최대공약수로 나눠주면서 출력한다.