[Baekjoon] 2251번: 물통

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

2251번: 물통

문제 설명

문제 이해는 어렵지 않다. 물통 A, B, C가 있고 처음엔 C만 채워진 상태로 주어진다. 그 다음 물통의 물을 다른 물통으로 옮기다가 A 물통이 비었을 때의 C 물통에 담겨 있는 물의 양을 알아놓았다가 오름차순으로 출력하면 된다.

예제 입력으로 예를 들면 다음과 같다.

처음 상태

A 물통이 비어있으므로 현재 C 물통에 차있는 만큼인 10을 정답에 추가한다.

C에서 B로 물을 옮겼다. A가 비어있고 C엔 나머지인 1만큼 있으므로 1을 정답에 추가한다.

B에서 A로 옮김

그 다음 B에서 A로 물을 옮겼다. A가 현재 물이 있으므로 넘어간다.

C에서 B로 옮김

C에서 B로 물을 옮겼다. A가 현재 물이 있으므로 넘어간다.

A에서 C로 옮김

A에서 C로 물을 옮겼다. A가 비어있고 C에 물이 8만큼 있으므로 정답에 8을 추가한다.

 

이런 식으로 모든 경우를 따져보면 된다. 물통의 물을 옮기는 경우의 수는 6가지이다.

1. A -> B
2. A -> C
3. B -> A
4. B -> C
5. C -> A
6. C -> B

풀이 방법

완전 탐색 방법 중 BFS를 활용하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class Main {

    static int A, B, C;
    static boolean[][][] isVisited;
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        setup();
        bfs();
        printAnswer();
    }

    private static void setup() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        A = Integer.parseInt(split[0]);
        B = Integer.parseInt(split[1]);
        C = Integer.parseInt(split[2]);

        isVisited = new boolean[A + 1][B + 1][C + 1];
    }

    private static void bfs() {
        Queue<BucketState> q = new LinkedList<>();
        q.add(new BucketState(0, 0, C));

        while (!q.isEmpty()) {
            BucketState curBS = q.poll();
            
            // 이미 확인한 경우 패스
            if (isVisited[curBS.a][curBS.b][curBS.c])
                continue;

            isVisited[curBS.a][curBS.b][curBS.c] = true;

            // A가 비어있으면 C값 저장
            if (curBS.a == 0)
                ans.add(curBS.c);

            // B to A
            if (curBS.a + curBS.b > A) { // 두 합이 A보다 크면 A를 가득 채우고 나머지는 B에 둔다.
                q.add(new BucketState(A, curBS.a + curBS.b - A, curBS.c));
            } else { // 두 합이 A보다 작거나 같으면 전부 A로 옮긴다.
                q.add(new BucketState(curBS.a + curBS.b, 0, curBS.c));
            }

            // C to A
            if (curBS.a + curBS.c > A) { // 두 합이 A보다 크면 A를 가득 채우고 나머지는 C에 둔다.
                q.add(new BucketState(A, curBS.b, curBS.a + curBS.c - A));
            } else { // 두 합이 A보다 작거나 같으면 전부 A로 옮긴다.
                q.add(new BucketState(curBS.a + curBS.c, curBS.b, 0));
            }

            // A to B
            if (curBS.b + curBS.a > B) { // 두 합이 B보다 크면 B를 가득 채우고 나머지는 A에 둔다.
                q.add(new BucketState(curBS.b + curBS.a - B, B, curBS.c));
            } else { // 두 합이 B보다 작거나 같으면 전부 B로 옮긴다.
                q.add(new BucketState(0, curBS.b + curBS.a, curBS.c));
            }

            // C to B
            if (curBS.c + curBS.b > B) { // 두 합이 B보다 크면 B를 가득 채우고 나머지는 C에 둔다.
                q.add(new BucketState(curBS.a, B, curBS.c + curBS.b - B));
            } else { // 두 합이 B보다 작거나 같으면 전부 B로 옮긴다.
                q.add(new BucketState(curBS.a, curBS.c + curBS.b, 0));
            }

            // A to C
            if (curBS.c + curBS.a > C) { // 두 합이 C보다 크면 C를 가득 채우고 나머지는 A에 둔다.
                q.add(new BucketState(curBS.c + curBS.a - C, curBS.b, C));
            } else { // 두 합이 C보다 작거나 같으면 전부 C로 옮긴다.
                q.add(new BucketState(0, curBS.b, curBS.c + curBS.a));
            }

            // B to C
            if (curBS.c + curBS.b > C) { // 두 합이 C보다 크면 C를 가득 채우고 나머지는 B에 둔다.
                q.add(new BucketState(curBS.a, curBS.c + curBS.b - C, C));
            } else { // 두 합이 C보다 작거나 같으면 전부 C로 옮긴다.
                q.add(new BucketState(curBS.a, 0, curBS.c + curBS.b));
            }
        }
    }

    private static void printAnswer() {
        Collections.sort(ans);
        StringBuilder sb = new StringBuilder();
        for (Integer i : ans) {
            sb.append(i).append("\n");
        }
        System.out.print(sb);
    }

    private static class BucketState {
        int a;
        int b;
        int c;

        public BucketState(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}