🔍 문제

📌 입력

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

📌 출력

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

📝 코드

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


public class Main {
    static int A, B, C;
    static boolean[][][] visited;
    static ArrayList<Integer> cBottle = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        A = Integer.parseInt(st.nextToken()); //A 물병 용량
        B = Integer.parseInt(st.nextToken()); //B 물병 용량
        C = Integer.parseInt(st.nextToken()); //C 물병 용량

        visited = new boolean[A + 1][B + 1][C + 1]; // 0 ~ Limit 까지

        bfs(0, 0, C);

        Collections.sort(cBottle);

        for (int cBottle : cBottle){
            bw.write(cBottle + " ");
        }

        bw.flush();
        bw.close();
    }

    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 bfs(int a, int b, int c) {
        Queue<Bottle> q = new LinkedList<>();
        q.offer(new Bottle(a, b, c)); //초기 시작 물병
        //C만 가득 차 있음

        while (!q.isEmpty()) {
            Bottle nowB = q.poll(); //현재 물통 값 배열

            if (visited[nowB.a][nowB.b][nowB.c] == true) { //거쳐갔던 Bottle , Skip
                continue;
            }

            visited[nowB.a][nowB.b][nowB.c] = true; //방문 true

            if (nowB.a == 0) {
                //A 물통이 비어있을때
                //C 물통의 값은 무조건 저장
                if (!cBottle.contains(nowB.c)) { //여태까지 값중 중복되지 않은 값이라면
                    cBottle.add(nowB.c); //C값 저장
                }
            }

            // C -> A
            if (nowB.a + nowB.c <= A) { //현재 Bottle A 와 C의 물통의 합이 A전체 용량보다 작다면
                //몰아주기
                q.offer(new Bottle(nowB.a + nowB.c, nowB.b, 0));
            } else {
                //A물통 전부 채우기
                //A를 가득 채우기 위하여 사용된 용량만큼 C 차감
                q.offer(new Bottle(A, nowB.b, nowB.a + nowB.c - A));
            }
            // C -> B
            if (nowB.b + nowB.c <= B) {
                q.offer(new Bottle(nowB.a, nowB.b + nowB.c, 0));
            } else {
                q.offer(new Bottle(nowB.a, B, nowB.b + nowB.c - B));
            }
            //B -> A
            if (nowB.a + nowB.b <= A) {
                q.offer(new Bottle(nowB.a + nowB.b, 0, nowB.c));
            } else {
                q.offer(new Bottle(A, nowB.a + nowB.b - A, nowB.c));
            }
            //B -> C
            if (nowB.b + nowB.c <= C) {
                q.offer(new Bottle(nowB.a, 0, nowB.b + nowB.c));
            } else {
                q.offer(new Bottle(nowB.a, nowB.b + nowB.c - C, C));
            }
            //A -> B
            if (nowB.a + nowB.b <= B) {
                q.offer(new Bottle(0, nowB.a + nowB.b, nowB.c));
            } else {
                q.offer(new Bottle(nowB.a + nowB.b - B, B, nowB.c));
            }
            //A -> C
            if (nowB.a + nowB.c <= C) {
                q.offer(new Bottle(0, nowB.b, nowB.a + nowB.c));
            } else {
                q.offer(new Bottle(nowB.a + nowB.c - C, nowB.b, C));
            }
        }
    }

}

📗 정리

해당 문제를 풀기 위해서 물통의 물이 옮겨질 수 있는 모든 경우의 수를 계산 해야한다.
위 코드 처럼 모든 경우의 수를 분리해서 하나하나 코드에 써 내려가는 것을 싫어하는 편이라서 다른 방식으로 풀어보려 했으나 딱히 방법이 생각 나지 않았다.

Bottle nowB = q.poll();

if (visited[nowB.a][nowB.b][nowB.c] == true) { 
	continue;
}

visited[nowB.a][nowB.b][nowB.c] = true; 

평소 Queue 에서 데이터를 poll 한 후 visited 처리를 해주는 것 보다는 dfs를 재귀 하기전 미리 처리 해주는 것을 선호 한다.
하지만 전 처리를 하는 순간 경우의 수마다 코드의 중복이 발생해서 어쩔 수 없이 poll 한 후 처리 하도록 했다.
원래 코드 풀이 습관 에서 조금만 벗어나는 순간 문제를 푸는 속도가 확연하게 느려진다고 느껴졌다.

다양한 개념을 풀어보면서 적응 해 가는게 해결 방안 인 것 같다.