유클리드 호제법 -2 자바 백준 BOJ 1033 칵테일

이전 글 https://sh1mj1-log.tistory.com/136 에서 계속됩니다.

 

백준 1033 칵테일

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

1033번: 칵테일

 

 

1. 문제 분석

문제에서는 N-1 개의 비율로 N 개의 재료와 관련된 전체 비율을 알아낼 수 있다고 합니다. 

 

그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있습니다. 그래서 임의의 노드에서 DFS 혹은 BFS 를 진행하면서 정답을 찾으면 됩니다.

DFS 과정에서 유클리드 호제법을 사용해서 비율들의 최소 공배수와 최대 공약수를 구하고, 재료의 최소 질량을 구하는 데 사용해서 문제를 해결하면 됩니다.

 

2. 손으로 풀기

1. 인접 리스트를 이용해서 각 재료의 비율 자료를 그래프로 구현.

 

2. 데이터를 저장할 때마다 비율과 관련된 수들의 최소공배수를 업데이트.

여러 노드를 그래프에 저장할 때마다 p와 q 의 값에 대한 최소공배수를 구하고 lcm 에 해당 최소공배수를 곱하면 결과적으로 모든 수에 대한 최소 공배수를 구할 수 있습니다.

 

3. 임의의 시작점에 최대 공배수 값을 저장합니다.

 

임의의 시작점이 0 이라고 하면 D[0] = 105 가 됩니다.

 

4. 임의의 시작점에서 DFS 로 탐색으 수행하면서 각 노드의 값을 이전 노드 값과의 비율 계산을 통해서 계산하고 저장합니다.

 

만약 0 을 임의의 점으로 선정하면  0 -> 4 -> 1 -> 2 -> 3 으로 탐색할 것입니다.

이전 단계에서 시작 노드 0 에 대해 D[0] = 105를 해두었습니다.

4 => 0번 노드값 * 1/1 = 105 

1 => 4번 노드값 * 1/3 = 35

2 => 4번 노드값 * 1/5 = 21

3 => 4번 노드값 * 1/7 = 15

5. 각 노드의 값을 모든 노드의 최대 공약수로 나눈뒤 출력합니다. 

 

완성된 비율의 합이 최소값이 아닐 수 있기 때문에 모든 값을 최대 공약수로 나누는 작업도 해주어야 합니다.

105, 35, 21, 15, 105 의 최대 공약수는 1이기 때문에 이 경우 정답은 105 35 21 15 105 가 됩니다.

 

3. 슈도코드

N: 재료 개수, A: 그래프, lcm: 최소공배수
D: 각 노드값 저장 배열, visitied: DFS 탐색 시 탐색 여부 저장 배열
변수 초기화 수행
for(에지 개수){
    인접 리스트 배열에 이 에지 정보 저장
    최소 공배수 업데이트
}

0 번 노드에 최소 공배수 저장.
0번 에서 DFs 탐색 수행
DFS 후 업데이트 된 D 배열의 값들의 최대 공약 수 계산
D 배열의 각 값들을 최대 공약수로 나눠서 정답 출력

// 최대 공약수 gcd() 함수 구현
gcd{
    if(b == 0) -> a 가 최대 공약수
    else -> gcd(작은 수, 큰수 % 작은 수)
}

// DFS 메소드
DFS{
    visitied 배열에 현재 노드 방문 기록
    현재 노드의 연결 노드 중 방문하지 않은 노드로
    다음 노드의 값 = 현재 노드의 값 * 비율 로 저장
    DFS 실행(재귀 형태)
}

// 노드 클래스
class cNode{
    다음 노드, 비율 1, 비율 2
}

4. 코드

public class BaekJun1033Book {
    static ArrayList<cNode>[] A;
    static long lcm;
    static boolean visited[];
    static long D[];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        A = new ArrayList[N];
        visited = new boolean[N];
        D = new long[N];
        lcm = 1;
        for (int i = 0; i < N; i++) {
            A[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();
            A[a].add(new cNode(b, p, q));
            A[b].add(new cNode(a, q, p));
            lcm *= (p * q / gcd(p, q));
        }
        D[0] = lcm;
        dfsFunc(0);

        // 수를 하나씩 비교해가면서 D 에 있는모든 수에 대해 최대공약수 구하기
        long mgcd = D[0];
        for (int i = 1; i < N; i++) {
            mgcd = gcd(mgcd, D[i]);
        }
        for (int i = 0; i < N; i++) {
            System.out.print(D[i] / mgcd + " ");
        }
    }

    static void dfsFunc(int Node) {
        visited[Node] = true;
        for (cNode adjNode : A[Node]) {
            int next = adjNode.node;
            if (!visited[next]) {
                D[next] = D[Node] * adjNode.q / adjNode.p; // 주어진 비율로 다음 노드값 갱신
                dfsFunc(next);
            }
        }
    }

    static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    static class cNode {
        int node;
        int p;
        int q;

        public cNode(int node, int p, int q) {
            this.node = node;
            this.p = p;
            this.q = q;
        }
    }
}

 

 

이 문제는 어떻게 풀지도 떠올렸고 그래프를 적용해서 DFS 혹은 BFS 을 적용해야 하는 것까지도 눈치챘지만 구현을 제대로 못해서 시간이 굉장히 오래걸렸네요... 그다지 어려운 문제는 아닌데 말이죠... 골드 2는 골드 2네요