문제

아이디어

세 물통의 특정 상태에서 전이할 수 있는 다음 상태가 제한적이다.
BFS, DFS를 이용한 그래프 탐색 문제로 해석할 수 있다. 혹은 백트래킹을 이용한다면 직관적으로 풀이할 수 있을 것 같다.
나는 BFS를 이용해 풀었다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][][] visited;
    static boolean[] cVisited;
    static Queue<Bottle> queue;

    static class Bottle {
        int A, B, C;

        Bottle(int A, int B, int C) {
            this.A = A;
            this.B = B;
            this.C = C;
        }
    }

    static void moveWater(int A, int B, int C) {
        if (!visited[A][B][C]) {
            visited[A][B][C] = true;
            if (A == 0) {
                cVisited[C] = true;
            }
            queue.add(new Bottle(A, B, C));
        }
    }

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

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        visited = new boolean[A + 1][B + 1][C + 1];
        cVisited = new boolean[C + 1];
        visited[A][B][C] = true;


        queue = new LinkedList<>();
        queue.add(new Bottle(0, 0, C));
        cVisited[C] = true;

        Bottle b;
        while (!queue.isEmpty()) {
            b = queue.poll();

            // A -> B
            if (b.A + b.B > B) {
                moveWater((b.A + b.B) - B, B, b.C);
            } else {
                moveWater(0, b.A + b.B, b.C);
            }
            // A -> C
            if (b.A + b.C > C) {
                moveWater((b.A + b.C) - C, b.B, C);
            } else {
                moveWater(0, b.B, b.A + b.C);
            }
            // B -> A
            if (b.B + b.A > A) {
                moveWater(A, (b.A + b.B) - A, b.C);
            } else {
                moveWater(b.A + b.B, 0, b.C);
            }
            // B -> C
            if (b.B + b.C > C) {
                moveWater(b.A, (b.B + b.C) - C, C);
            } else {
                moveWater(b.A, 0, b.B + b.C);
            }
            // C -> A
            if (b.C + b.A > A) {
                moveWater(A, b.B, (b.C + b.A) - A);
            } else {
                moveWater(b.A + b.C, b.B, 0);
            }
            // C -> B
            if (b.C + b.B > B) {
                moveWater(b.A, B, (b.C + b.B) - B);
            } else {
                moveWater(b.A, b.B + b.C, 0);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= C; i++) {
            if (cVisited[i]) sb.append(i).append(' ');
        }

        System.out.println(sb);
    }
}

채점결과

BFS 과정이 상당히 더러워 보이지만 돌아가기만 하면 그만이다.
샤워하다가 출력 부분을 개선할 수 있을 것 같아서 수정 후 제출하였다.
8ms의 무의미한 개선을 이루어냈다.