[코딩테스트] 백준 1033 자바

백준 1033

백준 1033 문제

해당 문제에서는 n-1개의 비율로 n개의 재료와 관련된 전체 비율을 알아낼 수 있다고 한다. 이것을 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다.

이 내용을 바탕으로 임의의 노드에서 dfs를 진행하면서 정답을 찾으면 된다. dfs 과정에서 유클리드 호재법을 사용해 비율들의 최소 공배수와 최대 공약수를 구하고, 재료의 최소 질량을 구하는데 사용해 문제를 해결할 수 있다.

import java.util.*;

public class Boj1033 {

    private static List<Node>[] edgeList;
    private static long lcm;
    private static boolean[] visited;
    private static long[] distance;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 재료 개수
        edgeList = new ArrayList[n]; // 인접 리스트
        visited = new boolean[n]; // dfs를 탐색할 때 탐색 여부 저장 배열
        distance = new long[n]; // 각 노드값 저장 배열
        lcm = 1; // 최소 공배수

        // 인접 리스트 초기화
        for (int i = 0; i < n; i++) {
            edgeList[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();

            // 인접 리스트 배열에 에지 정보를 저장
            edgeList[a].add(new Node(b, p, q));
            edgeList[b].add(new Node(a, q, p));

            lcm *= (p * q / gcd(p, q)); // 최소 공배수 업데이트 (최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것)
        }

        distance[0] = lcm; // 0번 노드에 최소 공배수 저장
        dfs(0); // 0번에서 dfs 탐색 수행

        long mgcd = distance[0]; // 최대 공약수

        // dfs를 이용해 업데이트된 distance 배열의 값들의 최대 공약수를 계산
        for (int i = 1; i < n; i++) {
            mgcd = gcd(mgcd, distance[i]);
        }

        // distance 배열의 각 값들을 최대 공약수로 나눠 정답 출력
        for (int i = 0; i < n; i++) {
            System.out.print(distance[i] / mgcd + " ");
        }
    }

    // 촤대 공약수 gcd() 함수 구현
    private static long gcd(long a, long b) {
        if (b == 0) { // b가 0이면
            return a; // a가 최대 공약수
        } else {
            // 재귀 함수 형태로 구현
            return gcd(b, a % b);
        }
    }

    // 깊이 우선 탐색 함수 구현
    private static void dfs(int num) {
        visited[num] = true; // visited 배열에 현재 노드 방문 기록

        for (Node n : edgeList[num]) { // 현재 노드의 연결 노드 중
            int next = n.getB();

            if (!visited[next]) { // 방문하지 않은 노드로
                // 주어진 비율로 다음 노드값 갱신
                distance[next] = distance[num] * n.getQ() / n.getP(); // 다음 노드 값 = 현재 노드 값 * 비율로 저장
                dfs(next); // 재귀 형태의 dfs 실행
            }
        }
    }

    static class Node {

        int b; // 다음 노드
        int p; // 비율 1
        int q; // 비율 2

        public Node(int b, int p, int q) {
            this.b = b;
            this.p = p;
            this.q = q;
        }

        public int getB() {
            return b;
        }

        public int getP() {
            return p;
        }

        public int getQ() {
            return q;
        }
    }
}

풀이

1. 재료 개수를 입력 받아 n에 저장한다.
2. 인접 리스트 edgeList 크기를 n만큼 선언한다.
3. 탐색 여부 저장 배열 visited 크기를 n만큼 선언한다.
4. 각 노드값 저장 배열 distance 크기를 n만큼 선언한다.
5. 최소 공배수 lcm를 1로 초기화한다.
6. edgeList 크기만큼 반복하며, ArrayList를 초기화 해준다.
7. 에지 개수만큼 반복하며 edgeList 배열에 에지 정보를 저장한다.
8. lcm을 업데이트한다.
   8-1. 최대 공배수는 두 수의 곱을 최대 공약수로 나눈 것이다.
   8-2. gcd()로 최대 공약수를 구한다.
   8-3. gcd()는 유클리드 호재법으로 최대 공약수를 구한다.
   8-4. 두 번째 인자 b가 0이면 첫 번째 인자 a가 최대 공약수가 되기 때문에 a를 반환한다.
   8-5. b가 0이 아니면 더 나눌 수 있기 때문에 재귀 함수 형태로 반복하며 최대 공약수를 구한다.
9. edgeList[0]에 lcm을 저장한다.
10. 0번에서 dfs() 탐색을 수행한다.
    10-1. visited 배열에 현재 노드 방문을 기록한다.
    10-2. 현재 노드의 연결 노드 중 방문하지 않은 노드로 주어진 비율로 다음 노드값을 갱신한다. (다음 노드 값 = 현재 노드 값 * 비율)
    10-3. 재귀 함수 형태로 dfs()를 호출한다.
11. 최대 공약수 mgcd에 distance[0]를 저장한다.
12. dfs()를 이용해 업데이트된 distance 배열의 값들의 최대 공약수를 계싼한다.
13. distance 배열의 각 값들을 최대 공약수로 나눠 정답을 출력한다.