[백준 2251] 물통 -JAVA // le_effort//

쉽게 풀릴줄 알았는데 고생한 문제다...

고려해야 하는 조건은

물통 A B C

A->B

A->C

B->A

B->C

C->A

C->B

이렇게 옮길수 있는 모든 경우의수를 확인해주면 되는데

한 번 방문 했던 좌표 a물의양, b물의양 , c물의양 은 굳이 할 필요가 없으니 continue를 해주면 된다

 

또 고려해야 할 조건이 있는데, 물을 정해진 양 만큼 부을수 있는게 아니라

부을 통에 꽉찰때까지 부으므로

 

예를 들어, A물통에 있는 물을 B물통으로 옮긴다고 할 때

A물통에 있는 물을 B물통에 다 부어도 B물통이 수용할수 있는가 ? (B물통의 총 용량을 넘지 않는가)

이것만 조건 분류를 해주면 된다.

 

import java.io.*;
import java.util.*;
public class Main {
    static boolean visited[][][];
    static int max_a,max_b,max_c;
    static ArrayList<Integer>list = new ArrayList<>();
    static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t =br.readLine().split(" ");
        max_a = Integer.parseInt(t[0]);
        max_b = Integer.parseInt(t[1]);
        max_c = Integer.parseInt(t[2]);
        visited = new boolean[max_a+1][max_b+1][max_c+1];
        q.add(new Node(0,0,max_c));
        bfs();
        Collections.sort(list);
        for(int i=0; i<list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            Node node = q.poll();
            if(visited[node.a][node.b][node.c]) {
                continue;
            }
            if(node.a==0) {
                list.add(node.c);
            }
            visited[node.a][node.b][node.c] = true;
            
            if(node.a+node.b<=max_a) {
                q.add(new Node(node.a+node.b,0,node.c));
            }
            else {
                q.add(new Node(max_a,node.b+node.a-max_a,node.c));
            }
            if(node.a+node.c<=max_a) {
                q.add(new Node(node.a+node.c,node.b,0));
            }
            else {
                q.add(new Node(max_a,node.b,node.c+node.a-max_a));
            }
            if(node.b+node.a<=max_b) {
                q.add(new Node(0,node.a+node.b,node.c));
            }
            else {
                q.add(new Node(node.a+node.b-max_b,max_b,node.c));
            }
            if(node.b+node.c<=max_b) {
                q.add(new Node(node.a,node.b+node.c,0));
            }
            else {
                q.add(new Node(node.a,max_b,node.c+node.b-max_b));
            }
            if(node.c+node.a<=max_c) {
                q.add(new Node(0,node.b,node.c+node.a));
            }
            else {
                q.add(new Node(node.a+node.c-max_c,node.b,max_c));
            }
            if(node.c+node.b<=max_c) {
                q.add(new Node(node.a,0,node.c+node.b));
            }
            else {
                q.add(new Node(node.a,node.b+node.c-max_c,max_c));
            }
        }
    }
}
class Node{
    int a,b,c;
    Node(int a, int b ,int c){
        this.a=a;
        this.b=b;
        this.c=c;
    }
}