[ BOJ ][JAVA][2251] 물통

www.acmicpc.net/problem/2251

2251번: 물통

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	8233	3966	2929	48.566%

문제

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

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

입력

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

출력

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

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

코드

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

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

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<3; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int [] from = {0, 0, 1, 1, 2, 2}; 
        int [] to = {1, 2, 0, 2, 0, 1};
        boolean [][]check = new boolean[201][201];
        boolean [] ans = new boolean[201];
        Queue<Pair> q = new LinkedList<>();

        q.add(new Pair(0, 0));
        check[0][0] = true;
        ans[a[2]] = true;

        while (!q.isEmpty()) {
            Pair p = q.poll();
            int x = p.x;
            int y = p.y;
            int z = a[2]-x-y;

            for (int k=0; k<6; k++) {
                int [] next = {x, y, z};
                next[to[k]] += next[from[k]];
                next[from[k]] = 0;

                if (next[to[k]] > a[to[k]]) { //물통의 용량보다 물이 많을 때
                    next[from[k]] = next[to[k]] - a[to[k]]; //초과하는 만큼 다시 넣어주고
                    next[to[k]] = a[to[k]]; //용량에 가득 찬 물을 넣어준다.
                }
                if (!check[next[0]][next[1]]) {
                    check[next[0]][next[1]] = true;
                    q.add(new Pair(next[0], next[1]));
                    if (next[0] == 0) {
                        ans[next[2]] = true;
                    }
                }
            }
        }
        for (int i=0; i<=a[2]; i++) {
            if (ans[i])
                System.out.print(i+ " ");
        }
    }

}
class Pair {
    int x;
    int y;

    public Pair (int x, int y) {
        this.x = x;
        this.y = y;
    }
}