[BOJ] 2251 - 물통 JAVA

www.acmicpc.net/problem/2251

2251번: 물통

문제

각각 부피가 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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Bottle {
    int a;
    int b;
    int c;
    Bottle(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;

    static int[] mBottle;  // ([0] = A, [1] = B, [2] = C) 의 용량(= 크기)
    static boolean[][][] check = null;  // [A][B][C]
    static ArrayList<Integer> ans = null;
    static Queue<Bottle> que = null;

    public static void pourWater(int from, int to, int[] pBottle) {  // from은 반드시 비어있지 않아야한다.
        // from, to는 pBottle의 인덱스
        // pBottle = {a, b, c}
        int[] temp = {pBottle[0], pBottle[1], pBottle[2]};

        if(temp[from] + temp[to] <= mBottle[to]) {  // from의 물을 다 붓는 경우
            temp[to] += temp[from];
            temp[from] = 0;
        }else {  // to가 꽉 찰때까지만 붓는 경우
            temp[from] -= mBottle[to] - temp[to];  // to의 남은 공간만큼만 붓는다.
            temp[to] = mBottle[to];  // to는 꽉 차게 된다.
        }

        int nowA = temp[0], nowB = temp[1], nowC = temp[2];
        if(!check[nowA][nowB][nowC]) {
            que.add(new Bottle(nowA, nowB, nowC));
            check[nowA][nowB][nowC] = true;
            if(nowA == 0) ans.add(nowC);  // A == 0 일 때, C값 저장
        }
    }

    public static void bfs(int a, int b, int c) {
        que = new ArrayDeque<>();
        que.add(new Bottle(a, b, c));
        check[a][b][c] = true;
        ans.add(c);

        while(!que.isEmpty()) {
            Bottle bottle = que.poll();
            int[] pBottle = {bottle.a, bottle.b, bottle.c};

            if(pBottle[0] != 0) {  // from A
                if(pBottle[1] != mBottle[1]) pourWater(0, 1, pBottle);
                if(pBottle[2] != mBottle[2]) pourWater(0, 2, pBottle);
            }
            if(pBottle[1] != 0) {  // from B
                if(pBottle[0] != mBottle[0]) pourWater(1, 0, pBottle);
                if(pBottle[2] != mBottle[2]) pourWater(1, 2, pBottle);
            }
            if(pBottle[2] != 0) {  // from C
                if(pBottle[0] != mBottle[0]) pourWater(2, 0, pBottle);
                if(pBottle[1] != mBottle[1]) pourWater(2, 1, pBottle);
            }
        }
    }

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

        mBottle = new int[3];
        mBottle[0] = Integer.parseInt(st.nextToken());
        mBottle[1] = Integer.parseInt(st.nextToken());
        mBottle[2] = Integer.parseInt(st.nextToken());
        check = new boolean[mBottle[0] + 1][mBottle[1] + 1][mBottle[2] + 1];
        ans = new ArrayList<>();

        bfs(0, 0, mBottle[2]);
        Collections.sort(ans);
        for(int c : ans) {
            System.out.print(c + " ");
        }
    }
}

 

어려운 문제는 아닌데 구현으로 시간을 꽤 잡아먹었다.

 

DFS, BFS 뭘 사용하든 상관없어보인다.

 

노드의 개수 = 숫자 3개의 합으로 200을 만드는 모든 경우의 수

에지의 개수 = 6개 (한 물통에서 한 물통으로 물을 옮기는 경우의 수)

 

check[][][] 으로 8MB를 사용한다. 메모리 제한에 충분히 여유롭긴 하지만 뭔가 낭비되는 게 많은 느낌.

 

200*200*200으로 하지 않고 A+B+C<=200 으로 딱 가고 싶으면 

map<Bottle, boolean> 으로 처리할 수도 있을 듯.