백준 2251: 물통 [Java] - 포포

문제

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

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

입력

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

출력

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

예제 입력 1 

1 2 8 9 10

예제 출력 1 

8 9 10

https://www.acmicpc.net/problem/2251

2251번: 물통

---

정말 오랜만에 알고리즘 문제를 풀었다.
사실 bfs 카테고리에 있는 문제라 해결할 수 있었던 것 같다.. 
visit[][][]이라는 삼중 배열을 생성한 뒤, 방문 체크를 하면서 해결해야 한다.

물통이 3개 존재하므로 물을 옮길 수 있는 방법은 총 6가지다.

A -> B, C (2가지)
B -> A, C (2가지)
C -> A, B (2가지)

물을 한 번씩 옮기면서 visit[A물통에 담겨있는 물의 양][B물통에 담겨있는 물의 양][C물통에 담겨있는 물의 양] 을 방문했는지 체크해주는 것이다.

만약 방문하지 않았다면, A물통에 담겨있는 물의 양이 0인 경우 정답리스트에 담아주도록 한다.
이후 정답 리스트를 정렬해서 출력하면 되겠다.

**참고로 물을 옮길 때, 예를 들어 A -> B로 옮기는 상황이라면 현재 A물통과 B물통에 담긴 물을 합쳤을 때 B 병의 용량보다 클 수도, 작을 수도 있다.
만약 A 물  + B 물 > B 최대용량 이라면 A -> B로 물을 옮긴 결과, 
B 물통은 꽉차게되고, A물통은 A 물통의 물의 양 + B 물통의 물의 양 - B 물통의 전체 용량만큼 남아있게 된다.
아래 그림을 보면 쉽게 이해할 수 있다..

반대로 B 물통의 용량이 빵빵해서, A +  B를 해도 B 물통이 널널하다면 A 물통에는 0, B 물통에는 A + B 만큼의 물이 담기게 된다.
이것을 이해하고 코드로 풀어내는 것이 핵심인 듯하다.

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

public class Main {
    static int a, b, c;
    static boolean[][][] visit;
    static List<Integer> answer = new ArrayList<>();
    static Queue<Bottle> qu = new LinkedList<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        visit = new boolean[a + 1][b + 1][c + 1];

        bfs();

        Collections.sort(answer);

        for (int a : answer) {
            System.out.print(a + " ");
        }
    }

    private static void bfs() {
        qu.offer(new Bottle(0, 0, c));

        while (!qu.isEmpty()) {
            Bottle bottle = qu.poll();

            if(visit[bottle.a][bottle.b][bottle.c]) continue;

            if (bottle.a == 0) {
                answer.add(bottle.c);
            }

            visit[bottle.a][bottle.b][bottle.c] = true;

            // a -> b
            if(bottle.a + bottle.b <= b){
                qu.offer(new Bottle(0, bottle.a + bottle.b, bottle.c));
            } else {
                qu.offer(new Bottle(bottle.a + bottle.b - b, b, bottle.c));
            }

            // a -> c
            if(bottle.a + bottle.c <= c){
                qu.offer(new Bottle(0, bottle.b, bottle.a + bottle.c));
            } else {
                qu.offer(new Bottle(bottle.a + bottle.c - c, bottle.b, c));
            }

            // b -> a
            if(bottle.b + bottle.a <= a){
                qu.offer(new Bottle(bottle.a + bottle.b, 0, bottle.c));
            } else {
                qu.offer(new Bottle(a, bottle.a + bottle.b - a, bottle.c));
            }

            // b -> c
            if(bottle.b + bottle.c <= c){
                qu.offer(new Bottle(bottle.a, 0, bottle.b + bottle.c));
            } else {
                qu.offer(new Bottle(bottle.a, bottle.b + bottle.c - c, c));
            }

            // c -> a
            if(bottle.c + bottle.a <= a){
                qu.offer(new Bottle(bottle.a + bottle.c, bottle.b, 0));
            } else {
                qu.offer(new Bottle(a, bottle.b, bottle.c + bottle.a - a));
            }

            // c -> b
            if(bottle.c + bottle.b <= b){
                qu.offer(new Bottle(bottle.a, bottle.b + bottle.c, 0));
            } else {
                qu.offer(new Bottle(bottle.a, b, bottle.c + bottle.b - b));
            }

        }

    }
    static class Bottle{
        int a;
        int b;
        int c;

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