[BOJ 2251] 물통 - JAVA, Gold5

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

2251번: 물통

사용한 알고리즘 : BFS

 

풀이전략

 

모든 경우의 수를 BFS를 사용해 완전탐색하는 문제이다.

 

물통에서 물을 옮길 수 있는 경우의 수는 총 6가지로,

1. A물통-> B물통

2. A물통-> C물통

3. B물통 -> A물통

4. B물통 -> C물통

5. C물통 -> A물통

6. C물통 -> B물통

이 있다.

 

그런데 물을 옮길 때 조건으로

한 물통이 빌 때까지 물을 다른 물통에 쏟거나, 다른 물통이 가득찰 때까지 부어야 한다.

 

그렇기 때문에 물통 A에 물이 x리터있고 물통 B에 물이 y리터 있을 때

물통 A에서 물통 B로 물을 쏟아부을 수 있는 부피는 Math.min(x,B-y)이다.

 

이유는 아래 그림과 같이 x>B-y이면

A물통의 물 x리터를 B로 모두 다 옮길 수 없어 B-y리터만 옮길 수 있기 때문이다. 

 

반대로 x<=B-y이면

물통 A의 모든 물 x리터를 물통 B로 옮길 수 있어 Math.min(x,B-y) 만큼의 물을 이동시킬 수 있는 것이다. 

물론 이는 A물통->B물통으로 물을 옮길 때만의 수식이었고,

다른 경우의 모든 수식을 각자 작성해 BFS 알고리즘을 완성시키면 된다.

 

그 과정 속에서 visited 이중 배열을 사용하여 (x,y) 경우의 수에 대한 중복을 방지하고

 

x=0인 경우, z=C-x-y 값을 저장해둔다.

 

그리고 BFS 탐색이 끝나면 z로 나올 수 있는 저장해둔 모든 경우의 수를 오름차순으로 출력하면 된다.

(나는 TreeSet을 사용하여 중복되지않으면서 오름차순으로 출력되도록 하였다.)

 

 

제출코드

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

public class Main {
    static int A,B,C;
    static class Node{
        int x;
        int y;
        int z;

        public Node(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }
    static boolean visited[][];
    static TreeSet<Integer> set = new TreeSet<>();

    static boolean pour(int x,int y){
        if(!visited[x][y]){
            visited[x][y]=true;
            return true;
        }
        return false;
    }

    static void bfs(){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0,0,C));
        visited[0][0]=true;

        while(!q.isEmpty()){
            Node now = q.poll();

            if(now.x==0){
                set.add(now.z);
            }

            // x->y
            int water = Math.min(now.x,B-now.y);
            if(pour(now.x-water,now.y+water)){
                q.offer(new Node(now.x-water,now.y+water,C-(now.x-water)-(now.y+water)));
            }

            // x->z
            water = Math.min(now.x,C-now.z);
            if(pour(now.x-water,now.y)){
                q.offer(new Node(now.x-water,now.y,now.z+water));
            }

            // y->x
            water = Math.min(now.y,A-now.x);
            if(pour(now.x+water,now.y-water)){
                q.offer(new Node(now.x+water,now.y-water,C-(now.x+water)-(now.y-water)));
            }

            // y->z
            water = Math.min(now.y,C-now.z);
            if(pour(now.x, now.y-water)){
                q.offer(new Node(now.x, now.y-water,C-now.x-(now.y-water)));
            }

            // z->x
            water = Math.min(now.z,A-now.x);
            if(pour(now.x+water,now.y)){
                q.offer(new Node(now.x+water,now.y,C-(now.x+water)-now.y));
            }

            // z->y
            water = Math.min(now.z,B-now.y);
            if(pour(now.x,now.y+water)){
                q.offer(new Node(now.x,now.y+water,C-now.x-(now.y+water)));
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        visited = new boolean[A+1][B+1];

        bfs();

        for(int x:set){
            bw.write(x+" ");
        }
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}