[Java] 백준 2251번 - 물통

문제 링크 : https://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

 

 

---

접근 방법

이 문제는 처음 문제를 보고 뜻을 잘 이해해야한다. 

[한 물통이 비거나, 다른 한 물통이 가득 찰 때까지] 물을 옮길 수 있다고 하였다.

이 문장의 뜻은 A물통에서 B물통으로 물을 옮긴다고 하였을 때, 

B물통이 다 차지 않고 A물통에도 물이 남아 있는데 -> 물을 옮기는 것을 멈출 수 없다는 뜻이다.

이렇게 되면 물을 쏟아 부을 때 총 두가지 케이스로 나뉘게 된다. 

1)  A -> B 일 때, B가 넘치는 경우

2) A -> B 일 때, B가 넘치지 않는 경우

 

 

그리고 물통은 총 A,B,C이므로 from 물통과 to물통의 경우는 아래와 같이 총 6가지로 나뉘게 된다.

A->B

B->A

B->A

B->C

C->A

C->B

 

위 6가지 각각의 경우에 대해 bfs를 활용하여 "A물통이 비었을 때 C물통에 있는 물의 양" 모든 케이스를 조사해보자. 

이때, 조사 완료된 케이스를 어떻게 체크할까?

A,B,C 물통의 물의 양 상태를 배열의 인덱스로 활용하면 된다. 즉, 물통에 1,2,3씩 물이 담겨 있는 상태고 이 상태에서 A,C물통의 조건을 조사했다면 visited[1][2][3] = true로 저장하면 된다.  코드는 아래와 같다.

import java.util.*;
public class BOJ_2251_물통옮기기 {

    public static class Water{
        int a, b, c;
        public Water(int a, int b, int c){
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    static ArrayList<Integer> ansList;
    static int capaA, capaB, capaC;
    static boolean[][][] visited = new boolean[201][201][201];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        ansList = new ArrayList<>();

        capaA = sc.nextInt();
        capaB = sc.nextInt();
        capaC = sc.nextInt();

        bfs();
        Collections.sort(ansList);
        for(int i = 0; i<ansList.size(); i++){
            System.out.print(ansList.get(i) + " ");
        }System.out.println();
    }

    public static void bfs(){

        Queue<Water> que = new LinkedList<Water>();
        que.add(new Water(0,0,capaC)); //초기 값 셋팅 (처음엔 C만 차 있음)
        //visited[0][0][capaC] = true;

        while(!que.isEmpty()){
            //검사한 케이스면 패스
            Water water = que.poll();
            int a= water.a;
            int b = water.b;
            int c = water.c;
           // System.out.println(a + " " + b + " " + c +" ");
            if(visited[a][b][c] == true) continue;

            //검사 안 했으면 체크하고
            visited[a][b][c] = true;
            //A 물통 비었으면 그 케이스 카운트
            if(a==0) ansList.add(c);

            // 물 옮기기. 물이 넘칠 때와 넘치지 않을 때 각각 나눠서
            //A -> B
            if(a + b >= capaB){ que.add(new Water(a-(capaB-b), capaB, c));} //옮기면 넘치는 경우
            else { que.add(new Water(0, a+b, c)); }
            //A -> C
            if(a + c >= capaC) { que.add(new Water(a-(capaC-c), b, capaC));}
            else { que.add(new Water(0, b, a+c)); }
            //B -> A
            if(b + a >= capaA){ que.add(new Water(capaA, b-(capaA-a), c)); }
            else { que.add(new Water(b+a, 0, c)); }
            //B -> C
            if(b + c >= capaC){ que.add(new Water(a, b-(capaC-c), capaC)); }
            else { que.add(new Water(a, 0, b+c)); }
            //C -> A
            if(c + a >= capaA) { que.add(new Water(capaA, b, c-(capaA-a)));}
            else{ que.add(new Water(a+c, b, 0)); }
            //C -> B
            if(c + b >= capaB) { que.add(new Water(a, capaB, c-(capaB-b)));}
            else{ que.add(new Water(a, b+c, 0)); }
        }

    }

}