문제사항

골드 5단계 문제였다.

사실 처음 이 문제를 접근했을 때는 이해를 제대로 못하였다.

너무 복잡하게만 생각한게 독이 된 듯 싶었다.

되려 문제를 있는 그대로 받아들이고, 토시 하나 빠뜨리지 않고 시뮬레이션을 해보는게 중요한 것 같다.

여기서 제일 중요한 문장은 첫번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양 이다.

1. 처음에는 앞의 두 물통(A, B)은 비어 있고, 세 번째 물통(C)은 가득 차 있다.

2. 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있다.

3. 이때, 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다.

이 과정을 순서대로 거치면서 첫 번째 물통(A)이 비어 있을 때마다 세 번째 물통(C)에 담겨있는 물의 양을 구하면 된다.

경우의 수를 생각해보면 물통에서 물을 옮기는 방법은 아래와 같이 6가지 이다.

1. A->B
2. B->A
3. B->C
4. C->B
5. A->C
6. C->A

두 묶음씩 묶어서 케이스 분류를 하였다.

A와 B물통끼리 크로스, B와 C물통끼리 크로스, A와 C물통끼리 크로스 하여 로직을 구현하였다.

예시를 들어 설명하자면,

1. A물통 + B물통의 물의 양이 B물통의 물의 양보다 크면 (water.a+water.b>b) B물통의 모두 물을 따라버린다면 넘쳐버리기 때문에 B물통에는 해당 용량만큼 가득 따라주고, A물통과 B물통의 물의 양을 합친 물에 B물통의 용량을 빼서 A물통에 따라주면 된다.

2. 반대로 A물통 + B물통의 물의 양이 B물통의 물의 양보다 작으면 (water.a+water.b<b) A물통과 B물통의 물의 양을 합친 물을 B물통에 모두 따라주고, A물통엔 0을 할당해준다.

이렇게 한 케이스로 분류되고 나머지 2개의 케이스도 동일하게 구현해주면 된다.

알고리즘 분류

1. 그래프

2. BFS, DFS

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Water {
        int a;
        int b;
        int c;
        public Water(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    static int a, b, c;
    static ArrayList<Integer> answer = new ArrayList<>();
    static boolean[][][] visited = new boolean[201][201][201];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        Queue<Water> que = new LinkedList<Water>();
        que.add(new Water(0, 0, c));

        while (!que.isEmpty()) {
            Water water = que.poll(); // 반환 후 삭제

            if (visited[water.a][water.b][water.c]) {
                continue;
            } else {
                visited[water.a][water.b][water.c] = true;
            }

            if (water.a == 0) { //첫 번째 물통(용량이 A인)이 비어 있을 때
                answer.add(water.c); //세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양
            }

            /** 총 6개의 경우의 수 (a,b)(b,a)(b,c)(c,b)(a,c)(c,a) **/

            /* (a,b)와 (b,a) */
            // b물통의 물을 a물통의 물에 합치려 할때, a물통이 넘친다면
            if (water.a + water.b > a) {
                // a물통에 전체 용량만큼 채우고, 나머지 물의 양은 b에 할당
                que.add(new Water(a, water.a + water.b - a, water.c));
            } else {
                // 넘치지 않으면 a물통에 모두 할당
                que.add(new Water(water.a + water.b, 0, water.c));
            }
            // a물통의 물을 b물통의 물에 합치려 할때, b물통이 넘친다면
            if (water.a + water.b > b) {
                // b물통에 전체 용량만큼 채우고, 나머지 물의 양은 a에 할당
                que.add(new Water(water.a + water.b - b, b, water.c));
            } else {
                // 넘치지 않으면 b물통에 모두 할당
                que.add(new Water(0, water.a + water.b, water.c));
            }

            /* (b,c)와 (c,b) */
            // c물통의 물을 b물통의 물에 합치려 할때, b물통이 넘친다면
            if (water.b + water.c > b) {
                // b물통에 전체 용량만큼 채우고, 나머지 물의 양은 c에 할당
                que.add(new Water(water.a, b, water.b + water.c - b));
            } else {
                // 넘치지 않으면 b물통에 모두 할당
                que.add(new Water(water.a, water.b + water.c, 0));
            }
            // b물통의 물을 c물통의 물에 합치려 할때, c물통이 넘친다면
            if (water.b + water.c > c) {
                // c물통에 전체 용량만큼 채우고, 나머지 물의 양은 b에 할당
                que.add(new Water(water.a, water.b + water.c - c, c));
            } else {
                // 넘치지 않으면 c물통에 모두 할당
                que.add(new Water(water.a, 0, water.b + water.c));
            }

            /* (a,c)와 (c,a) */
            // c물통의 물을 a물통의 물에 합치려 할때, a물통이 넘친다면
            if (water.a + water.c > a) {
                // a물통에 전체 용량만큼 채우고, 나머지 물의 양은 c에 할당
                que.add(new Water(a, water.b, water.a + water.c - a));
            } else {
                // 넘치지 않으면 a물통에 모두 할당
                que.add(new Water(water.a + water.c, water.b, 0));
            }
            // a물통의 물을 c물통의 물에 합치려 할때, c물통이 넘친다면
            if (water.a + water.c > c) {
                // c물통에 전체 용량만큼 채우고, 나머지 물의 양은 a에 할당
                que.add(new Water(water.a + water.c - c, water.b, c));
            } else {
                // 넘치지 않으면 c물통에 모두 할당
                que.add(new Water(0, water.b, water.a + water.c));
            }
        }

        TreeSet<Integer> set = new TreeSet<>();
        for (int a : answer) {
            set.add(a);
        }

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            sb.append(iterator.next()).append(" ");
        }

        System.out.println(sb);
    }
}

출처

[java 백준] 실버 1/2251번 물통