[백준 2251] 물통 / 자바 / 브루트포스(dfs or bfs) **

#문제         

레벨: G5
알고리즘: dfs or bfs
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

 

물을 옮기는 방법은 6가지이다.{ (A->B)  ( A -> C)  ( B -> A)  (B -> C)  (C -> A)  (C -> B) } 
우린 물을 옮기는 6가지 방법을 계속 꼬리를 물어 탐색하면 되는 것이다. 구현은 어떻게 할 것인가? 이중 for문으로 구현하던가 4방향으로 움직이는 dx = {1,0,0,-1}  dy = {0,1,-1,0}처럼 from[], to[]로 구현하면된다. 그러면 언제 탐색을 멈춰야 하나? 세 물통의 담겨있는 용량을 방문한적 있을 때 멈춰야한다.

 

물통의 리터제한은 200리터이다. 리터제한이 작으니 visited[A+1][B+1][C+1]를 만들 수 있다.또한, C의 용량을 TreeSet으로 담을 수도 있고, visited[A+1][B+1][C+1]로 세 용량을 나타내듯 boolean배열인 answer[C+1]로 나타낼 수 있다. 

 

위 로직은 dfs or bfs로 구현할 수 있다. 어차피 브루트포스이기 때문에 편한 알고리즘을 선택하면 된다. 그러나 dfs는 재귀호출 때문에 스택에 메로리가 쌓이니 메모리 효율성 방면으로 bfs로 구현하는 것이 좋다.

 

---

#풀이 코드      

 

DFS코드

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

public class Main {
    static int A, B, C;
    static boolean[][][] visited;
    static Set<Integer> answer;
    static int[] capacity;

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

        capacity = new int[]{A, B, C};
        visited = new boolean[A + 1][B + 1][C + 1];
        answer = new TreeSet<>(); // TreeSet을 사용하여 자동으로 정렬

        dfs(0, 0, C);

        for (int amount : answer) {
            System.out.print(amount + " ");
        }
    }

    static void dfs(int a, int b, int c) {
        if (visited[a][b][c]) return;
        
        visited[a][b][c] = true;
        
        if (a == 0) answer.add(c);

        // 모든 가능한 물 이동 방법을 시도
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j) {
                    int[] next = pour(new int[]{a, b, c}, i, j);
                    dfs(next[0], next[1], next[2]);
                }
            }
        }
    }

    static int[] pour(int[] state, int from, int to) {
        int[] next = state.clone();
        int amount = Math.min(state[from], capacity[to] - state[to]);
        next[from] -= amount;
        next[to] += amount;
        return next;
    }
}

 

BFS코드

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

public class Main {
    static int A, B, C;
    static boolean[][][] visited;
    static boolean[] answer;
    static int[] from = {0, 0, 1, 1, 2, 2};
    static int[] to = {1, 2, 0, 2, 0, 1};

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

        visited = new boolean[A + 1][B + 1][C + 1];
        answer = new boolean[C + 1];

        bfs();

        for (int i = 0; i <= C; i++) {
            if (answer[i]) {
                System.out.print(i + " ");
            }
        }
    }

    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, C});
        visited[0][0][C] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int a = cur[0], b = cur[1], c = cur[2];

            if (a == 0) answer[c] = true;

            for (int i = 0; i < 6; i++) {
                int[] next = {a, b, c};
                next[to[i]] += next[from[i]];
                next[from[i]] = 0;

                if (next[to[i]] > new int[]{A, B, C}[to[i]]) {
                    next[from[i]] = next[to[i]] - new int[]{A, B, C}[to[i]];
                    next[to[i]] = new int[]{A, B, C}[to[i]];
                }

                if (!visited[next[0]][next[1]][next[2]]) {
                    visited[next[0]][next[1]][next[2]] = true;
                    queue.offer(next);
                }
            }
        }
    }
}