[Algo] 백준 2251 물통 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/2251

메모리 : 23408KB

시간 : 152ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    static Set<Integer> ans;
    static boolean[][][] check;
    static int A, B, C;

    public static <T> void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        check = new boolean[A + 1][B + 1][C + 1];
        ans = new TreeSet<>();
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { 0, 0, C });
        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            if (check[tmp[0]][tmp[1]][tmp[2]])
                continue;
            if (tmp[0] == 0) {
                ans.add(tmp[2]);
            }
            check[tmp[0]][tmp[1]][tmp[2]] = true;
            // c->b
            if (B >= tmp[2] + tmp[1]) { // 다 부을 수 있으면
                q.add(new int[] { tmp[0], tmp[1] + tmp[2], 0 });
            } else { // 다 부을 수 없으면
                // B에 붓고 나머지 A에 공간에 넣기
                if (tmp[2] - (B - tmp[1]) <= A - tmp[0]) {
                    q.add(new int[] { tmp[0] + (tmp[2] - (B - tmp[1])), B, 0 });
                }
                // C에 남기기 단 B에 자리가 있어야 변동이 있음
                if (B - tmp[1] > 0) {
                    q.add(new int[] { tmp[0], B, tmp[2] - (B - tmp[1]) });
                }
            }
            // c->a
            if (tmp[2] <= A - tmp[0]) {
                q.add(new int[] { tmp[0] + tmp[2], tmp[1], 0 });
            } else {
                if (tmp[2] - (A - tmp[0]) <= (B - tmp[1])) {
                    q.add(new int[] { A, tmp[1] + (tmp[2] - (A - tmp[0])), 0 });
                }
                if (A - tmp[0] > 0) {
                    q.add(new int[] { A, tmp[1], tmp[2] - (A - tmp[0]) });
                }
            }
            // a->b
            if (tmp[0] <= B - tmp[1]) { // 다 부을 수 있으면
                q.add(new int[] { 0, tmp[1] + tmp[0], tmp[2] });
            } else { // 다 부을 수 없으면
                // B에 붓고 나머지 C에 공간에 넣기
                if (tmp[0] - (B - tmp[1]) <= (C - tmp[2])) {
                    q.add(new int[] { 0, B, tmp[2] + (tmp[0] - (B - tmp[1])) });
                }
                // A에 남기기 단 B에 자리가 있어야 변동이 있음
                if (B - tmp[1] > 0) {
                    q.add(new int[] { tmp[0] - (B - tmp[1]), B, tmp[2] });
                }
            }
            // a->c
            if (tmp[0] <= C - tmp[2]) { // 다 부을 수 있으면
                q.add(new int[] { 0, tmp[1], tmp[2] + tmp[0] });
            } else { // 다 부을 수 없으면
                // C에 붓고 나머지 B에 공간에 넣기
                if (tmp[0] - (C - tmp[2]) <= (B - tmp[1])) {
                    q.add(new int[] { 0, tmp[1] + (tmp[0] - (C - tmp[2])), C });
                }
                // A에 남기기 단 C에 자리가 있어야 변동이 있음
                if (C - tmp[2] > 0) {
                    q.add(new int[] { tmp[0] - (C - tmp[2]), tmp[1], C });
                }
            }
            // b->c
            if (tmp[1] <= C - tmp[2]) { // 다 부을 수 있으면
                q.add(new int[] { tmp[0], 0, tmp[2] + tmp[1] });
            } else { // 다 부을 수 없으면
                // C에 붓고 나머지 A에 공간에 넣기
                if (tmp[1] - (C - tmp[2]) <= (A - tmp[0])) {
                    q.add(new int[] { tmp[0] + (tmp[1] - (C - tmp[2])), 0, C });
                }
                // B에 남기기 단 C에 자리가 있어야 변동이 있음
                if (C - tmp[2] > 0) {
                    q.add(new int[] { tmp[0], tmp[1] - (C - tmp[2]), C });
                }
            }
            // b->a
            if (tmp[1] <= A - tmp[0]) { // 다 부을 수 있으면
                q.add(new int[] { tmp[0] + tmp[1], 0, tmp[2] });
            } else { // 다 부을 수 없으면
                // A에 붓고 나머지 C에 공간에 넣기
                if (tmp[1] - (A - tmp[0]) <= (C - tmp[2])) {
                    q.add(new int[] { A, 0, tmp[2] + (tmp[1] - (A - tmp[0])) });
                }
                // B에 남기기 단 A에 자리가 있어야 변동이 있음
                if (A - tmp[0] > 0) {
                    q.add(new int[] { A, tmp[1] - (A - tmp[0]), tmp[2] });
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i : ans) {
            sb.append(i + " ");
        }
        System.out.print(sb);
    }
}

풀이

조합으로 삼차원디피를 해보려했으나ㅋㅋㅋ 그냥 하나하나 하면 되는 문제였다.