1. 문제 설명 📌

(1) 링크🔗

문제 링크

(2) 해설🕵

A,B,C 물통의 용량이 주어지고, A,B는 비어 있는 상태, C는 가득찬 상태로 주어진다.
A 물통이 비어 있을 수 있는 모든 경우의 수에서 C에 찬 물의 용량을 출력 하시오

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: Back-tracking

이 문제를 처음보고, 하노이의 탑이 떠올랐다. 이유는 다음과 같다.

하나의 물통에서 다른 물통으로 전달할 수 있는 물의 용량이 정해짐

이 부분 때문에 물이라도, 보내질 양을 정형화할 수 있기 때문에, 하노이의 탑과 다를 바 없다고 느꼈다. 따라서 Back-tracking으로 문제를 풀었다.

이후 구현 방식

Bottle3라는 클래스를 만들어서, hashCode()와 equals() 함수를 초기화 했다. 이유는 *HashSet에 넣어서, 중복된 값은 카운트 하지 않기 위해서 *이다.
중복된 값이면 넘어가고, 처음보는 A,B,C 양상이면 SET에 넣는다.
만약 SET에 넣을 때 A가 0이면, C를 답변지 List에 저장한다.

(2) SUDO CODE 📜

+ 0. 세팅 - 물통 클래스를 만들어서, hashCode()와 equals 함수 초기화
+ 0. 입력값 받아서, A,B,C 최대 용량을 나타내는 volume 배열에 넣기
+ 1. Back-tracking 시작(from = 근원지, to = 표적,int [] arr 현 레벨 물의 양상 snapShot)
-    (1) from에서 to로 옮겨 담기
-    (2) 옮겨 담은 후 A,B,C의 물이 담긴 양상이 처음 보는 거면 SET에 넣고, 다음으로 넘어감
-        만약 한 번 본 양상이면, 이번 Back-tracking은 종료하고 부모 레벨로 돌아간다.
-    (3) A,B,C의 양상에서 A = 0 이면 C값을 답변 리스트에 저장한다.
-    (4) 현 양상에서 다시 옮겨 담기를 반복한다. from과 to를 현 Level과 똑같지 않고, from에 물이 담긴 거면 전부 시도

(3) 시간복잡도 분석 🕓

A,B,C 전체 물의 용량이 최대 200밖에 안되서 완탐으로 풀어도 가능한 수준이었다. 그래서 Back-Tracking을 선택했다.
다른 사람들의 풀이를 보니까, A,B,C 물통에서 나올 수 있는 모든 양상을 boolean [201][201][201] 로 표현해서,배열 내의 BFS로 문제를 푸신 분들도 있더라. 이 경우, 내 풀이보다 시간이 2배 빨랐다.

3. 구현 코드 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;


public class Main {

    static int [] volume = new int [3];
    static HashSet<Bottle3> set = new HashSet<>();
    static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        init();
        back_tracking(2, 0, new int []{0,0,volume[2]});
        back_tracking(2, 1, new int []{0,0,volume[2]});
        Collections.sort(ans);
        for (int answer : ans) {
            System.out.print(answer + " ");
        }
    }

    public static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        volume[0] = Integer.parseInt(st.nextToken());
        volume[1] = Integer.parseInt(st.nextToken());
        volume[2] = Integer.parseInt(st.nextToken());
    }

    public static void back_tracking(int from, int to, int [] arr) {
        // 계산 조건
        int origin_from = arr[from];
        arr[from] = (volume[to] - arr[to]) - arr[from] >= 0 ? 0 : arr[from] - (volume[to] - arr[to]);
        arr[to] = (volume[to] - arr[to]) - origin_from >= 0 ? arr[to] + origin_from : volume[to];
        Bottle3 now = new Bottle3(arr[0], arr[1], arr[2]);
        if(set.contains(now)) return;
        else {
            if(arr[0] == 0)ans.add(arr[2]);
            set.add(now);
        }


        for(int i = 0; i < 3; i++){
            if(arr[i] > 0) {
                for (int j = 0; j < 3; j++) {
                    if(i != j && (i != from && j != to)){
                        back_tracking(i, j, new int []{arr[0], arr[1], arr[2]});
                    }
                }
            }
        }
    }
}

class Bottle3 {
    int A;
    int B;
    int C;

    public Bottle3 (int A, int B, int C) {
        this.A = A;
        this.B = B;
        this.C = C;
    }
    @Override
    public boolean equals (Object obj) {
        if(obj.getClass()!= Bottle3.class) return false;

        return ((Bottle3) obj).A == this.A
                && ((Bottle3) obj).B == this.B
                && ((Bottle3) obj).C == this.C;
    }

    @Override
    public int hashCode() {
        return this.A + this.B + this.C;
    }
}