[알고리즘] 2251번

오늘 풀어볼 문제는 백준 2251번 문제이다.

문제

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

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

입력

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

출력

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

📌 도전 📌
Queue에 A, B 값을 한 번에 넣을 수 있게 AB라는 클래스를 선언한다. 이 Queue를 활용해서 BFS로 문제를 풀어나갔다.

public class Main {
    static int[] Sender = {0, 0, 1, 1, 2, 2}; // A A B B C C
    static int[] Receiver = {1, 2, 0, 2, 0, 1}; // B C A C A B
    static boolean visited[][];
    static boolean answer[];
    static int now[];

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

        now = new int[3];
        now[0] = Integer.parseInt(st.nextToken()); // A 용량 저장
        now[1] = Integer.parseInt(st.nextToken()); // B 용량 저장
        now[2] = Integer.parseInt(st.nextToken()); // C 용량 저장

        visited = new boolean[201][201]; // 최대 용량으로 배열 크기 설정
        answer = new boolean[201]; // 최대 용량으로 배열 크기 설정
        BFS();
        for (int i = 0; i < answer.length; i++) {
            if (answer[i]) {
                System.out.print(i + " ");
            }
        }
    }

    private static void BFS() {
        Queue<AB> queue = new LinkedList<>();
        queue.add(new AB(0, 0));
        visited[0][0] = true;
        answer[now[2]] = true;
        while(!queue.isEmpty()) {
            AB p = queue.poll();
            int A = p.A;
            int B = p.B;;
            int C = now[2] - A - B; // C 용량에서 A와 B를 뺌

            for(int k=0; k<6; k++) {
                int[] next = {A, B, C};
                next[Receiver[k]] += next[Sender[k]];
                next[Sender[k]] = 0;
                if(next[Receiver[k]] > now[Receiver[k]]) { // 초과한다면
                    next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]];
                    next[Receiver[k]] = now[Receiver[k]];
                }
                if(!visited[next[0]][next[1]]) {
                    visited[next[0]][next[1]] = true;
                    queue.add(new AB(next[0], next[1]));
                    if(next[0] == 0) {
                        answer[next[2]] = true;
                    }
                }
            }

        }
    }
}
class AB {
    int A;
    int B;
    public AB(int a, int b) {
        A = a;
        B = b;
    }
}

[문제 출처] : https://www.acmicpc.net/problem/2251