[2251] 물통

🔗 문제 링크

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

🔍 문제 설명

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

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

⚠️ 제한사항

• 각 용량은 오름차순으로 정렬한다.

🗝 풀이 (언어 : Java)

각각의 양동이의 물의 양을 그래프의 정점으로 생각하고, 서로 옮겨담는 경우들을 간선으로 생각해서 탐색을 수행하면 된다. 구현이 복잡해서 까다로운 문제였다. BFS로 구현했고 0~200까지 가능한 모든 정답 값 범위의 boolean배열의 인덱스로 선언해서 가능한 값을 표시했다. 이미 거쳐간 경우엔 중복을 막고자 세개의 양동이의 물양을 각각의 인덱스로한 boolean 3차원 배열로 체킹했다.

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

class Main {
    class State {
        int[] bucket;
        State(int[] b) {
            bucket = b;
        }
        State move(int from, int to, int[] limit) {
            int[] tmp = new int[] {bucket[0], bucket[1], bucket[2]};
            if (limit[to] < tmp[from] + tmp[to]) {
                tmp[from] -= (limit[to] - tmp[to]);
                tmp[to] = limit[to];
            } else {
                tmp[to] += tmp[from];
                tmp[from] = 0;
            }
            return new State(tmp);
        }
    }

    private boolean[] possible = new boolean[201];
    private boolean[][][] visited = new boolean[201][201][201];

    private String findCases(int[] limit) {
        Queue<State> queue = new LinkedList<>();
        // 첫 시작 큐에 넣기
        queue.add(new State(new int[] {0, 0, limit[2]}));
        visited[0][0][limit[2]] = true;
        // bfs
        while (!queue.isEmpty()) {
            State state = queue.poll();
            // 첫 양동이가 비었으면, 그 때의 세번째 양동이 값에 해당하는 인덱스 체크
            if (state.bucket[0] == 0)
                possible[state.bucket[2]] = true;
            // 해당 상태에서 일어날 수 있는 모든 상태
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == j) // 같은 양동이 경우 제외
                        continue;
                    // i번째 양동이의 물을 j번째 양동이로 옮기기
                    State tmp = state.move(i, j, limit);
                    // 만약 옮긴 상태가 전에 있었던 경우가 아니라면 방문체크, 큐에 넣기
                    if (!visited[tmp.bucket[0]][tmp.bucket[1]][tmp.bucket[2]]) {
                        visited[tmp.bucket[0]][tmp.bucket[1]][tmp.bucket[2]] = true;
                        queue.add(tmp);
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        // 정답출력
        for (int i = 0; i <= limit[2]; i++) {
            if (possible[i])
                sb.append(i).append(' ');
        }
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] limit = new int[3];
        for (int i = 0; i < 3; i++)
            limit[i] = Integer.parseInt(st.nextToken());
        System.out.print(new Main().findCases(limit));
    }
}