물통_2251.md

🚰 [2251] 물통

난이도: 골드 5
소요 시간: 30분
메모리: 11712KB
시간: 80ms

리뷰

• A와 C에 담은 물의 양을 기억하고, 다음에 같은 상황이 올 때 계산하지 않고 넘어간다..!

전체 코드

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

public class Main_bj2251 {

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

        int[] ABC = new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())};
        boolean[][] visited = new boolean[ABC[0]+1][ABC[2]+1];
        br.close();

        Queue<int[]> queue = new LinkedList<>();
        visited[0][ABC[2]] = true;
        queue.add(new int[] {0,0,ABC[2]});
        Set<Integer> set = new TreeSet<>();

        while(!queue.isEmpty()) {
            int[] node = queue.poll();
            if(node[0]==0) {
                set.add(node[2]);
            }

            for(int i=0; i<3; i++) {
                if(node[i]==0) continue;
                for(int j=0; j<3; j++) {
                    if(i==j) continue;
                    int[] tmp = node.clone();

                    if(node[i] > ABC[j]-node[j]) {
                        tmp[i] -= (ABC[j]-node[j]);
                        tmp[j] = ABC[j];
                    }else {
                        tmp[i] = 0;
                        tmp[j] += node[i];
                    }

                    if(!visited[tmp[0]][tmp[2]]) {
                        visited[tmp[0]][tmp[2]] = true;
                        queue.add(tmp);
                    }
                }

            }

        }

        StringBuilder sb = new StringBuilder();
        for(int item: set) {
            sb.append(item).append(" ");
        }
        System.out.println(sb);
    }
}