백준 2251 물통

문제

풀이

public class 물통 {
	
    // 물을 옮기는 쪽의 인덱스
    static int[] sender = {0, 0, 1, 1, 2, 2};
    // 물을 받는 쪽의 인덱스
    static int[] receiver = {1, 2, 0, 2, 0, 1};
    // 탐색한 물통a,b의 모든 경우의 수를 체크하기 위한 배열
    // a와 b만 따로 체크하는 이유는
    // a와 b에 들어있는 물의 양을 구하면 c물통에 들어있는 물의 양을 구할 수 있기 때문
    static boolean[][] visited;
    // 조건에 부합하는 물통c의 값을 저장하는 배열
    static boolean[] result;
    // 각 물통의 최대값을 저장할 배열
    static int[] now;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        now = new int[3];
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 물통 a, b, c의 최대값 저장
        now[0] = Integer.parseInt(st.nextToken());
        now[1] = Integer.parseInt(st.nextToken());
        now[2] = Integer.parseInt(st.nextToken());
        // 물통 a,b가 가질 수 있는 물의 양에 대한 경우의 수를 체크하는 배열
        visited = new boolean[201][201];
        // 조건에 맞는 물통c의 값을 저장할 배열
        result = new boolean[201];
        bfs();
        // result가 true라는 뜻은
        // bfs를 거치며 a물통이 비어졌을 때 물통 c의 값이라는 뜻이므로
        // result의 인덱스 값을 출력
        for (int i = 0; i < result.length; i++) {
            if (result[i]){
                System.out.print(i + " ");
            }
        }
    }

    public static void bfs() {
        Queue<AB> q = new LinkedList<>();
        // 처음에는 물통c만 가득 차 있는 상태이므로 a,b는 0으로 설정하고
        q.add(new AB(0, 0));
        // 이 때의 경우의 수를 기록
        visited[0][0] = true;
        // a가 비어있으므로 이때 c의 값을 기록
        result[now[2]] = true;
        while (!q.isEmpty()) {
            AB node = q.poll();
            // 물통a
            int a = node.a;
            // 물통b
            int b = node.b;
            // 물통c
            int c = now[2] - a - b;
            // 물을 옮겨 담을 수 있는 경우의 수
            // a에서는 b,c로 경우의 수가 2
            // b에서는 a,c로 2
            // c에서는 a,b로 2
            // 총 6가지
            for (int k = 0; k < 6; k++) {
            	// 물을 옮겨 담은 후의 결과를 저장할 배열
                int[] next = {a, b, c};
                // 각 경우의 수에 따라 물을 옮겨 담음
                next[receiver[k]] += next[sender[k]];
                // 물을 비운쪽의 물통은 0으로 설정
                next[sender[k]] = 0;
                // 물이 넘치면(물을 옮겨담은 결과가 물통의 최대값보다 크면)
                if (next[receiver[k]] > now[receiver[k]]) {
                    // 물을 비운쪽에는 옮겨담고 남은 물을 저장
                    next[sender[k]] = next[receiver[k]] - now[receiver[k]];
                    // 물을 옮긴 담은 통은 최대값으로 설정
                    next[receiver[k]] = now[receiver[k]];
                }
                // a물통과 b물통의 양이 기존에 나오지 않았던 값이면
                if (!visited[next[0]][next[1]]) {
                	// 해당 경우의 수를 체크하고
                    visited[next[0]][next[1]] = true;
                    // 큐에 a,b의 값을 담음
                    q.add(new AB(next[0], next[1]));
                    // 이때 a물통이 비어졌다면 결과 배열 result에 c물통의 값을 저장
                    if (next[0] == 0) {
                        result[next[2]] = true;
                    }
                }
            }
        }
    }
}
// 물통 a와 b의 값을 저장하기 위한 클래스
class AB{
    int a;
    int b;
    public AB(int a, int b) {
        this.a = a;
        this.b = b;
    }
}

리뷰

bfs를 사용하기는 했지만 여태 풀었던 문제와는 결이 좀 다른 문제였다.

일단 생각해보아야 할게 몇가지 있었는데,

1. 각 물통의 최대값을 유지해야 한다
   • 배열을 이용해 각 물통의 최대값을 저장해준다.
2. 물을 옮겨 담을 때마다 물통에 물이 얼마나 남아있는지 상태를 기억해야 한다.
   • 부피값(입력값)의 최대값만큼의 배열을 선언해 모든 경우의 수를 저장해준다.
3. bfs를 어떻게 구현하느냐의 문제가 있다.
   • 기존의 bfs문제는 에지 정보가 주어지기 때문에 저장되어 있는 값들을 활용하면 됐지만,
     여기서는 물을 옮기는 경우의 수를 직접 구현해줘야 한다.

경우의 수를 체크해야 하는 경우 배열의 인덱스를 이용해 값을 체크하는 방법이 자주 쓰이니 짚고 넘어가자.

으어어 알고리즘은 풀어도 풀어도 익숙해지지 않는거 같다ㅜㅜ