[Java] 백준 2251번 : 물통

1. 문제

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

2251번: 물통

 

 

2. 풀이 과정

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 Main {
    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);
    }
 
}

 

 

결과