[백준] 2251: 물통 - JAVA

08 Jul 2023 in Algorithm on 그래프 이론

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

풀이

물통 세 개의 부피가 정해져 있고 초기에는 C물통만 가득 차 있다.

A물통이 비어있을 때마다 C물통의 양을 체크하여 저장하면 되는 문제이다.

A, B, C물통의 양을 방문처리하기 위해 boolean[][][] 배열을 이용했고,

C물통의 양을 오름차순으로 저장하기 위해 TreeSet을 이용했다.

dfs탐색을 통해 진행하며 물통의 양을 체크했고,

A물통에 물이 있다면 “A물통의 양 + B물통의양”과 “B물통의 용량”을 비교하여 A물통에서 B물통으로 옮기는 경우를 처리했다.

---

메모리: 23284KB

시간: 140ms

언어: Java 11

코드

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

public class Main {
    static int A, B, C;
    static boolean[][][] visit;
    static TreeSet<Integer> set;

    public static 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());

        visit = new boolean[C + 1][C + 1][C + 1];
        set = new TreeSet<>();
        dfs(0, 0, C);

        StringBuilder sb = new StringBuilder();
        set.stream().forEach(num -> sb.append(num + " "));

        System.out.println(sb);
    }

    private static void dfs(int a, int b, int c) {
        if (visit[a][b][c]) {
            return;
        }

        if (a == 0) {
            set.add(c);
        }

        visit[a][b][c] = true;

        if (a > 0) {
            if (a + b > B) {
                dfs(a + b - B, B, c);
            } else {
                dfs(0, a + b, c);
            }

            if (a + c > C) {
                dfs(a + c - C, b, c);
            } else {
                dfs(0, b, a + c);
            }
        }

        if (b > 0) {
            if (b + c > C) {
                dfs(a, b + c - C, C);
            } else {
                dfs(a, 0, b + c);
            }

            if (b + a > A) {
                dfs(A, b + a - A, c);
            } else {
                dfs(b + a, 0, c);
            }
        }

        if (c > 0) {
            if (c + a > A) {
                dfs(A, b, c + a - A);
            } else {
                dfs(c + a, b, 0);
            }

            if (c + b > B) {
                dfs(a, B, c + b - B);
            } else {
                dfs(a, c + b, 0);
            }
        }
    }

}