백준 2251 물통(Java)

문제 출처 : https://www.acmicpc.net/problem/2251

2251번: 물통

문제 설명

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

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

입력

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

출력

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

풀이

DFS, BFS 탐색 문제인데, 고민했던 부분은 방문체크를 어떻게 할 지였다.

방문체크는 A, B에 부었던 물의 양으로 2차원 배열을 사용했다. A, B의 물의 양이 정해지면 C의 물의 양도 정해지기 때문에, 2차원 배열로 물통들의 상태를 방문 체크 해줄 수 있다.

 

아래 푼 방식은 DFS를 사용했다. A에 있는 물의 양이 0보다 크다면 B, C 각각 물을 붓는 DFS 탐색을 돌려준다. B, C도 마찬가지로 해주면 된다. 이미 해당 물의 양을 고려해줬다면 즉, 이미 visited[A][B]가 true면 탐색을 중단하도록 해준다.

 

결과는 오름차순으로 출력해야 하므로, 방문체크 배열에서 A가 0인 배열에서 B가 큰 값부터 visited[0][B]가 true면 C에 있는 물의 양을 계산해서 출력해준다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_2251 {
    static int volume[];
    static boolean visited[][];

    public static void dfs(int A, int B){
        int C = volume[2] - A - B;
        int spaceA = volume[0] - A;
        int spaceB = volume[1] - B;
        int spaceC = volume[2] - C;

        if(visited[A][B]) { return;}
        visited[A][B] = true;


        if(A > 0){
            int BW = Math.min(spaceB, A);
            dfs(A - BW, B + BW);
            int CW = Math.min(spaceC, A);
            dfs(A - CW, B);
        }
        if(B > 0){
            int AW = Math.min(spaceA, B);
            dfs(A + AW, B - AW);
            int CW = Math.min(spaceC, B);
            dfs(A, B - CW);
        }
        if(C > 0){
            int AW = Math.min(spaceA, C);
            dfs(A + AW, B);
            int BW = Math.min(spaceB, C);
            dfs(A, B + BW);
        }

    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        volume = new int[3];

        for(int i=0; i<3; i++){
            volume[i] = Integer.parseInt(st.nextToken());
        }

        visited = new boolean[volume[0]+1][volume[1]+1];
        dfs(0, 0);

        StringBuilder sb = new StringBuilder();
        for(int i=volume[1]; i>=0; i--){
            if(visited[0][i]){
                sb.append(volume[2] - i).append(" ");
            }
        }
        System.out.println(sb);
    }

}

결과