백준 2251 물통

피나코·2023년 2월 2일

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

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

접근 방식

발생할 수 있는 모든 경우(6가지)로 재귀함수를 돌려주었다.

A,B,C 물통의 상태가 반복되지 않게, 비교해주기 위해서 “A-B-C” 꼴의 문자열로 만들어주는 메소드를 만들어 주었다.

재귀를 돌면서 A가 0인 경우의 C를 resultSet자료구조에 담아주었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int[] bucket = new int[3];

    static Set<String> checkSet = new HashSet<>();

    static Set<Integer> resultSet = new HashSet<>();

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < 3; i++) bucket[i] = Integer.parseInt(st.nextToken());

        recur(0, 0, bucket[2]);

        List<Integer> myList = new ArrayList<>(resultSet);
        Collections.sort(myList);

        StringBuilder sb = new StringBuilder();

        for (int v : myList) sb.append(v).append(" ");

        System.out.println(sb);

    }

    private static void recur(int a, int b, int c) {
        if (checkSet.contains(makeHash(a, b, c))) return;

        checkSet.add(makeHash(a, b, c));

        if (a == 0) resultSet.add(c);

        int A = 0;
        int B = 0;
        int C = 0;

        if (a != 0) {
            //A -> B
            A = b + a > bucket[1] ? b + a - bucket[1] : 0;
            B = Math.min(b + a, bucket[1]);
            recur(A, B, c);

            //A -> C
            A = c + a > bucket[2] ? c + a - bucket[2] : 0;
            C = Math.min(c + a, bucket[2]);
            recur(A, b, C);
        }

        if (b != 0) {
            //B -> C
            B = c + b > bucket[2] ? c + b - bucket[2] : 0;
            C = Math.min(c + b, bucket[2]);
            recur(a, B, C);

            //B -> A
            A = Math.min(b + a, bucket[0]);
            B = b + a > bucket[0] ? b + a - bucket[0] : 0;
            recur(A, B, c);
        }

        if (c != 0) {
            //C -> A
            A = Math.min(c + a, bucket[0]);
            C = c + a > bucket[0] ? c + a - bucket[0] : 0;
            recur(A, b, C);

            // C -> B
            B = Math.min(c + b, bucket[1]);
            C = c + b > bucket[1] ? c + b - bucket[1] : 0;
            recur(a, B, C);
        }

    }

    private static String makeHash(int a, int b, int c) {
        return a + "-" + b + "-" + c;
    }

}