[BOJ] 2251 : 물통(Java)

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

---

💡 풀이

처음에 이 문제를 보고 어떻게 접근을 해야할까 하고 생각을 해보다 문제의 알고리즘 분류를 확인해봤다. 다름아닌 "그래프 탐색"으로 분류가 되어 있었다. 이 문제를 어떻게 그래프로 접근이 가능할까? 이런 접근 방법을 빠르게 파악하는 것이 중요한 것 같다. 천천히 살펴보자.

 

 물통들의 1가지 상태는 (a, b, c)와 같이 하나의 pair로 표현될 수 있다. 또한, 물을 붓는 행위를 거치면 (a, b, c)의 상태가 (a', b', c')으로 바뀌게 된다. 이를 다르게 생각해보면, (a, b, c) 상태는 정점의 의미가 될 수 있고, 물을 붓는 행위를 간선이라 볼 수 있다. 

위에 주어진 예를 들어보면, 초기값 (0, 0, 10)에 대해 (0, 9, 1) ← (0, 0, 10) → (8, 0, 2) 와 같은 방향 그래프로 나타낼 수 있는 것이다. 또한, 물통 A, B, C에 대해 물통에 넣을 수 있는 물의 범위가 최댓값으로 주어져 있기 때문에, pair의 개수가 많아도 201*201*201 개로 대략적으로 계산이 가능한 수치이다.

 

결론적으로 이 문제에서의 그래프는

• 정점 = $O(8*10^6)$
• 간선 = $O(8*10^6*6)$ (물통 사이에 이동할 수 있는 가지 수 = 6)

이기 때문에, BFS이던 DFS이던, 시간 복잡도는 모두 $O(8*10^6)$이 된다. 

 

구현

이를 그래프로 구현하기 위해, 하나의 구조체를 선언할 필요가 있다.

// 물통의 현재 상태(정점)와 물을 붓는 행위(간선)를 관리하는 구조체
static class State{
    int[] bottles;

    State(int[] _bottles){
        bottles = new int[3];
        System.arraycopy(_bottles, 0, bottles, 0, 3);
    }

    /**
     * from 물통에서 to 물통으로 물을 옮기기
     * @param from : from 물통
     * @param to : to 물통
     * @param Limit : 각 물통의 최대 용량
     * @return 옮기고 난 뒤, 새로운 물통의 상태
     */
    State move(int from, int to, int[] Limit) {
        int[] nbottles = new int[]{bottles[0], bottles[1], bottles[2]};

        // 1. to 물통이 먼저 차는 경우
        if (bottles[from] + bottles[to] >= Limit[to]) {
            nbottles[from] -= Limit[to] - bottles[to];
            nbottles[to] = Limit[to];
        }
        // 2. from 물통이 바닥나는 경우
        else{
            nbottles[to] += nbottles[from];
            nbottles[from] = 0;
        }

        return new State(nbottles);
    }
}

이 클래스에는 int 배열이 존재하고 물통 A, B, C의 양 즉, (a, b, c)가 들어가게 된다. move() 함수는 물을 붓는 행위, 즉 간선에 해당하는 함수가 된다. 이 부분만 잘 구현한다면 탐색 부분은 쉽게 구현이 가능하다. 

 

 

전체적인 코드는 다음과 같다. 

package Graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Q2251 {
    static int[] Limit;
    static boolean[] possible;
    static boolean[][][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Limit = new int[3]; // 각각 a, b, c의 최대 용량
        for (int i = 0; i < 3; i++) {
            Limit[i] = sc.nextInt();
        }

        visited = new boolean[205][205][205]; // 상태마다 탐색 여부를 체크
        possible = new boolean[205]; // 만약 결과로 3이 나왔다면 possible[3] = true

        BFS(0, 0, Limit[2]);

        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i <= Limit[2]; i++) {
            if(possible[i])
                ans.add(i);
        }

        for (Integer an : ans) {
            System.out.println(an + " ");
        }
    }

    static void BFS(int a, int b, int c) {
        Queue<State> queue = new LinkedList<>();

        visited[a][b][c] = true;
        queue.add(new State(new int[]{a, b, c}));

        while (!queue.isEmpty()) {
            State s = queue.poll();

            // 만약 A 물통이 비어있다면 원하는 정답
            if (s.bottles[0] == 0) {
                possible[s.bottles[2]] = true;
            }

            // 모두 방문하기
            for (int from = 0; from < 3; from++) {
                for (int to = 0; to < 3; to++) {
                    // 같은 물통끼리는 수행할 수 없다.
                    if (from == to) continue;

                    State next = s.move(from, to, Limit);
                    // next 상태를 방문한 적이 없다면
                    if (!visited[next.bottles[0]][next.bottles[1]][next.bottles[2]]) {
                        queue.add(next);
                        visited[next.bottles[0]][next.bottles[1]][next.bottles[2]] = true;
                    }
                }
            }
        }
    }

    // 물통의 현재 상태(정점)와 물을 붓는 행위(간선)를 관리하는 구조체
    static class State{
        int[] bottles;

        State(int[] _bottles){
            bottles = new int[3];
            System.arraycopy(_bottles, 0, bottles, 0, 3);
        }

        /**
         * from 물통에서 to 물통으로 물을 옮기기
         * @param from : from 물통
         * @param to : to 물통
         * @param Limit : 각 물통의 최대 용량
         * @return 옮기고 난 뒤, 새로운 물통의 상태
         */
        State move(int from, int to, int[] Limit) {
            int[] nbottles = new int[]{bottles[0], bottles[1], bottles[2]};

            // 1. to 물통이 먼저 차는 경우
            if (bottles[from] + bottles[to] >= Limit[to]) {
                nbottles[from] -= Limit[to] - bottles[to];
                nbottles[to] = Limit[to];
            }
            // 2. from 물통이 바닥나는 경우
            else{
                nbottles[to] += nbottles[from];
                nbottles[from] = 0;
            }

            return new State(nbottles);
        }
    }
}