[BOJ] 2251. 물통 - (Java)

[BOJ] 2251. 물통 - (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 30M

난이도 : ★★

---

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

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

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

Input

첫째 줄에 세 정수 A, B, C가 주어진다.

Output

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

Example

input

8 9 10

output

1 2 8 9 10

Solution & Inpression

물통의 물을 옮기는 방법

from A to B

from A to C

from B to A

from B to C

from C to A

from C to B

모든 경우를 BFS 탐색 Set을 이용하여 중복을 제거한 뒤 List로 옮겨 정렬 후 출력

Code

언어 : JAVA

메모리 : 23520 kb

실행 시간 : 112 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int[] input;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = new int[3];
        input[0] = sc.nextInt();
        input[1] = sc.nextInt();
        input[2] = sc.nextInt();

        Queue<int[]> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        boolean[][][] visit = new boolean[input[0] + 1][input[1] + 1][input[2] + 1];
        visit[0][0][input[2]] = true;
        set.add(input[2]);
        q.offer(new int[] { 0, 0, input[2] });

        while (!q.isEmpty()) {
            int[] now = q.poll();
            if (now[0] == 0) {
                set.add(now[2]);
            }

            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == j)
                        continue;
                    int[] next = solve(now, i, j);
                    if (!visit[next[0]][next[1]][next[2]]) {
                        visit[next[0]][next[1]][next[2]] = true;
                        q.offer(next);
                    }
                }
            }
        }

        ArrayList<Integer> ans = new ArrayList<>(set);
        Collections.sort(ans);
        StringBuilder sb = new StringBuilder();
        for (Integer i : ans) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }

    private static int[] solve(int[] now, int i, int j) {
        if (now[i] == 0 || now[j] == input[j]) {
            return now;
        }

        // from i to j;
        int[] next = now.clone();
        int tmp = input[j] - next[j];
        if (next[i] > tmp) {
            next[j] += tmp;
            next[i] -= tmp;
        } else {
            next[j] += next[i];
            next[i] = 0;
        }

        return next;
    }
}