백준 2251번: 물통 (Java)

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

2251번: 물통

 

 

 

 

 

 

 

 

---

 

나의 접근 방법

숫자도 작고, 케이스도 얼마 안 많을 거 같아서 경우 나눠주면 될 거라고 생각했습니다. 그런데 경우 나누는게 꽤 빡세더라고요. 못 하겠어서 알고리즘 분류를 보고 풀었습니다.

 

풀이

A, B, C <= 200이므로, 800만개의 boolean을 저장하는 3차원 배열을 만들 수 있습니다.

각 경우마다 A에서 B, C, B에서 A, C, C에서 A, B로 물을 붓는, 총 6가지의 경우가 있습니다.

적당히 BFS, DFS를 수행하면 됩니다. 왠지 DFS가 더 깔끔한 듯합니다.

은근히 케이스 생각하기가 어렵습니다.

 

코드

풀이 1. BFS

import java.io.*;
import java.util.*;
 
public class Main {
    static int A, B, C;
    
    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());
        boolean[] ans = new boolean[201];
        boolean[][][] visited = new boolean[A+1][B+1][C+1];
        ans[C] = true;
        visited[0][0][C] = true;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {0, 0, C});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int[][] nxts = pour(cur);
            for (int i = 0; i < 6; i++) {
                if (visited[nxts[i][0]][nxts[i][1]][nxts[i][2]]) continue;
                visited[nxts[i][0]][nxts[i][1]][nxts[i][2]] = true;
                if (nxts[i][0] == 0 && !ans[nxts[i][2]]) ans[nxts[i][2]] = true;
                queue.offer(new int[] {nxts[i][0], nxts[i][1], nxts[i][2]});
            }
        }
        
        for (int i = 0; i <= 200; i++) {
            if (ans[i]) System.out.printf(i+" ");
        }
    }
    
    static int[][] pour(int[] cur) {
        int a = cur[0], b = cur[1], c = cur[2];
        int[][] ret = new int[6][3];
        // A -> B
        ret[0][0] = Math.max(a-(B-b), 0);
        ret[0][1] = Math.min(a+b, B);
        ret[0][2] = c;
        // A -> C
        ret[1][0] = Math.max(a-(C-c), 0);
        ret[1][1] = b;
        ret[1][2] = Math.min(a+c, C);
        // B -> A
        ret[2][0] = Math.min(a+b, A);
        ret[2][1] = Math.max(b-(A-a), 0);
        ret[2][2] = c;
        // B -> C
        ret[3][0] = a;
        ret[3][1] = Math.max(b-(C-c), 0);
        ret[3][2] = Math.min(b+c, C);
        // C -> A
        ret[4][0] = Math.min(a+c, A);
        ret[4][1] = b;
        ret[4][2] = Math.max(c-(A-a), 0);
        // C -> B;
        ret[5][0] = a;
        ret[5][1] = Math.min(b+c, B);
        ret[5][2] = Math.max(c-(B-b), 0);
        return ret;
    }
}
 

 

풀이 2. DFS

import java.io.*;
import java.util.*;
 
public class Main {
    static int A, B, C;
    static boolean[] ans;
    static boolean[][][] visited;
    
    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());
        ans = new boolean[201];
        visited = new boolean[A+1][B+1][C+1];
        dfs(0, 0, C);
        
        for (int i = 0; i <= 200; i++) {
            if (ans[i]) System.out.printf(i+" ");
        }
    }
    
    static void dfs(int a, int b, int c) {
        if (visited[a][b][c]) return;
        visited[a][b][c] = true;
        if (a == 0 && !ans[c]) ans[c] = true;
        
        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 + a > A) dfs(A, a+b-A, c);
        else dfs(a+b, 0, c);
        if (b + c > C) dfs(a, b+c-C, C);
        else dfs(a, 0, b+c);
        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);
    }
}