[백준] 2251 물통 java

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

public class Bottle {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static List<Integer> ans;
    static int[] cur = new int[3];
    static int[] capacity = new int[3];
    static HashSet<String> set;

    public static void main(String[] args) throws IOException{
        input();
        int[] arr = cur.clone();
        dfs(arr);
        Collections.sort(ans);
        for(int a : ans) {
            sb.append(a).append(" ");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 3; i++) {
            capacity[i] = Integer.parseInt(st.nextToken());
        }
        cur[0] = cur[1] = 0;
        cur[2] = capacity[2];
        ans = new ArrayList<>();
        set = new HashSet<>();
        set.add(Arrays.toString(cur));
    }

    static void dfs(int[] cur) {
        String curStr = Arrays.toString(cur);
        //리스트 추가 조건
        if(cur[0] == 0 && set.contains(curStr)) ans.add(cur[2]);

        for(int i = 0; i < 3; i++) {
            //각각 컵에 물이 담겨 있을 때 모든 경우의 수로 계산해야함
            if(cur[i] != 0) {
                for(int j = 0; j < 3; j++) {
                    if(j != i) {
                        int[] tmp = cur.clone();
                        int jCupCanCapacity = capacity[j] - cur[j];
                        if(tmp[i] <= jCupCanCapacity) {
                            tmp[j] += tmp[i];
                            tmp[i] = 0;
                        }
                        else {
                            tmp[j] += tmp[i] - (tmp[i] - jCupCanCapacity);
                            tmp[i] -= tmp[i] - (tmp[i] - jCupCanCapacity);
                        }
                        if(!set.contains(Arrays.toString(tmp))) {
                            set.add(Arrays.toString(tmp));
                            dfs(tmp);
                        }
                    }
                }
            }
        }
        return;
    }
}

완전탐색 dfs 문제였다. 자료구조는 배열과 set을 이용해서 풀었다. dfs로 풀어도 상관없고 bfs로 풀어도 상관없다.

 

큰 코드 흐름은 이렇다.

 

1. input에 맞게 입력을 받는다.

2. 초기값은 무조건 정답 중 하나이므로 set에 추가해준다.

3. 현재 물통의 상태에서 모든 물을 옮길 수 있는 경우의 수를 dfs 해준다. 다만 중복된 경우의 수를 계속해서 dfs 하면 무한루프에 빠질 수 있기 때문에 set을 통해서 중복은 제거해준다.

4. output을 오름차순 정렬 후 알맞게 출력해준다.

 

이 문제의 키포인트는 중복을 제거하며 모든 경우의 수를 탐색하는 것, 해당 경우의 수에서 물통에 물을 알맞게 옮기는 것 정도가 되겠다.

 

문제 풀 때 아직 시간이 조금 걸리는데 초반에 빨리 문제를 정의해서 논리적으로 흐름을 정리한 후에 구현하는 걸 연습을 해야겠다. 쉽지않아 ~>~