[ 백준/Java ] 2251. 물통

백준 링크 : https://www.acmicpc.net/problem/2251

 

🌱 [ 문제 요약 ]

 

최대 용량이 다른 물통 A,B,C가 있다. 처음엔 C물통만 가득 차 있다.

그런데 물통에서 다른 물통으로 물을 옮길수 있다.

( 단. 한통이 비거나 한통이 가득 찰 때까지 부어야 한다. )

이와 같은 과정을 반복할때 A물통이 비어 있을때,

C 물통에 담길수 있는 물의 양을 모두 구해 오름 차순으로 출력해라. ( 1 <= 물의양 <= 200 )

 

🌱 [ 알고리즘 선택 ]

모든 경우의 수를 구해야 하므로 브루트포스

인접한 물통에 옮기는 것을 반복 해야 하므로 BFS 선택

 

🔥 [ 물을 옮기는 방법 ]

 

만약 A 물통이 B 물통의 물을 모두 받아 드릴수 있다면 B 물통의 양만큼 옮길 수 있다.

 

 

하지만 A물통의 물을 B물통에 모두 부었을때 넘칠 수 있다.

옮길수 있는 물의 양은 물을 옮기는 A물통의 물의 양과

물을 붓는 대상인 B물통에 수용 가능한 물의양 ( 전체 수용량 - 현재 물의 양 ) 중 작은 값이다.

---

[ 전체 코드 ]

public class Main {

    public static final int MAX_BOTTLE_SIZE = 201;
    public static final int BOTTLE_TOTAL_SIZE = 3;
    static int[] maxWaterBottles;
    static boolean[][][] visited;
    static List<Integer> CBottleRemainWaters;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] waterBottleInput = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int aBottleSize = waterBottleInput[0];
        int bBottleSize = waterBottleInput[1];
        int cBottleSize = waterBottleInput[2];

        maxWaterBottles = new int[]{aBottleSize, bBottleSize, cBottleSize};
        visited = new boolean[MAX_BOTTLE_SIZE][MAX_BOTTLE_SIZE][MAX_BOTTLE_SIZE];
        CBottleRemainWaters = new ArrayList<>();

        bfs(0, 0, cBottleSize);

        CBottleRemainWaters.sort(Comparator.naturalOrder());
        StringBuilder sb = new StringBuilder();
        fillStringBuilderFromCBottleWater(sb);
        System.out.print(sb);
    }

    public static void bfs(int a, int b, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{a, b, c});
        visited[a][b][c] = true;
        CBottleRemainWaters.add(c);

        while (!queue.isEmpty()) {
            int[] bottles = queue.poll();

            for (int standardIndex = 0; standardIndex < BOTTLE_TOTAL_SIZE; standardIndex++) {
                for (int targetIndex = 0; targetIndex < BOTTLE_TOTAL_SIZE; targetIndex++) {

                    if (targetIndex == standardIndex) continue;
                    int[] nextBottles = copyBottle(bottles);

                    int moveWaterAmount = calculateMoveWaterAmount(nextBottles, standardIndex, targetIndex);
                    moveWater(nextBottles, moveWaterAmount, targetIndex, standardIndex);

                    if (!visited[nextBottles[0]][nextBottles[1]][nextBottles[2]]) {
                        visited[nextBottles[0]][nextBottles[1]][nextBottles[2]] = true;
                        queue.add(nextBottles);

                        if (isZeroRemainWaterFromABottle(nextBottles)) {
                            CBottleRemainWaters.add(nextBottles[2]);
                        }
                    }
                }
            }
        }
    }

    private static int[] copyBottle(int[] bottles) {
        int[] nextBottle = new int[3];
        System.arraycopy(bottles, 0, nextBottle, 0, BOTTLE_TOTAL_SIZE);
        return nextBottle;
    }

    private static int calculateMoveWaterAmount(int[] bottles, int standardIndex, int targetIndex) {
        int maxReceiveWaterToTarget = maxWaterBottles[targetIndex] - bottles[targetIndex];
        int maxMoveWaterFromStandard = bottles[standardIndex];
        return Math.min(maxReceiveWaterToTarget, maxMoveWaterFromStandard);
    }

    private static void moveWater(int[] nextBottles, int moveWaterAmount, int targetIndex, int standardIndex) {
        nextBottles[standardIndex] -= moveWaterAmount;
        nextBottles[targetIndex] += moveWaterAmount;
    }

    private static boolean isZeroRemainWaterFromABottle(int[] nextBottles) {
        return nextBottles[0] == 0;
    }

    private static void fillStringBuilderFromCBottleWater(StringBuilder sb) {
        for (int num : CBottleRemainWaters) {
            sb.append(num).append(" ");
        }
    }
}