백준 2251 물통 Java

BFS를 사용한 완전 탐색으로 풀어볼 문제인 물통이다.

문제 설명이 굉장히 간단하다.

왠지 설명이 간단할수록 이해하기 더 힘든 것 같다ㅠ

 

이 문제를 처음 본 날엔 머리가 안돌아가는 상태였던 건지

글을 쓰는 지금은 이해가 잘되는데 당시에는 문제가 이해가 안 됐었다.

 

간단하게 설명하자면

입력으로 주어지는 3개의 정수는 각각 A B C 물통의

용량이 주어진 것이고

 

시작은 A와 B가 비어있고 C에만 가득 찬 상태로 시작한다.

그리고 다른 물통에 물을 부을 때는 한 물통이 비거나, 가득 찰 때까지 부을 수 있다.

몇 리터씩만 부어주고 이런 게 안된다.

그렇게 물을 이리 부었다 저리 부었다 하다가 A가 비어있을 때

C에 있는 물의 양의 경우의 수를 모두 출력해주면 되는 문제이다.

 

물의 최대 리터는 200이기 때문에

물통 3개를 다 해보는 경우의 수로 계산해도 200*200*200로 넉넉하다. 그러므로

BFS를 통한 완전 탐색을 하고 그 와중에 A가 비어있을 때 C의 물의 양을 출력하면 된다.

 

다른 BFS문제와 비슷하게 물을 부을 수 있는 경우의 수를 전부 큐에 넣으면서 탐색하면 된다.

물을 부을 수 있는 경우의 수는 누구나 생각할 수 있는 그 6가지이다.

C -> A

C -> B

B -> A

B -> C

A -> B

A -> C

 

A, B, C로 큐에 저장하고

방문했는지 체크하려고 3차원 배열을 쓰고

이렇게 하면 수고스럽기 때문에 while문 안에서 C를 구할 때는

총 물의 양에서 A와 B값을 빼주는 방식으로 하고

큐에는 A와 B의 값만 방문했는지 체크한다. 또한 방문했는지는 A와 B값을 통한 2차원 배열로 처리한다.

계속 바뀌는 A와 B값이지만 처음 입력받을 당시의 C의 값이 총 물의 양이기 때문에

총 물의양 - A - B 를하면 C에 담긴 물의 양을 알 수 있는 것이다.

 

처리해야 하는 것은 몇 개 없다.

총 경우의 수 6가지 대로 물을 옮기고 큐에 A와 B를 넣고 방문 배열에 체크하고 

A가 비어있다면 C에 담긴 물의 양을 저장해뒀다 출력하면 된다.

 

단 주의해야 할 점은 물의 양이 물통의 용량을 초과했을 때이다.

각각의 용량이 8 9 10이고

현재 물이 0 9 1로 들어있을 때

B의 물을 A에 다 부으면

9 0 1로 A물통의 용량(8)을 초과한다.

이때 초과하는 만큼 다시 B물통에 물을 넣어줘서

8 1 1로 될 수 있도록 처리해줘야 한다.

 

코드를 통해 다시 한번 이해하자.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Q2251 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int [] a = new int[3];
 
        for(int i=0; i<3; i++) {
            a[i] = scan.nextInt();
        }
 
        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;
    }
}