[BFS] 백준 2251번 물통 - JAVA

 

처음에는 '물통에 있는 물을 어떻게 규칙적으로 움직이지?' 라는 생각에 빠졌다.

c->b, b->a 그 다음에는?... 흠...

설계가 떠오르지 않으니 당연히 알고리즘도 떠오르지 않았다 ㅋㅋ

 

---

1. 출처

---

 

2251번: 물통

 

• A, B, C 물통 3개가 있음, 최대 200리터까지 올 수 있음
• 처음에는 C 물통이 가득 차있음
• 물통에 물을 이리저리 옮기다가 A가 0일 때 C에 올 수 있는 물의 리터를 오름차순으로 출력

 

 

---

2. 설계

---

 

 

설계는 알고나면 간단했다.

현재 A, B, C 물통의 상황에서 어떤 상황을 연출할 수 있는지 가짓수를 전부 시뮬레이션 후 큐에 넣어주는 것을 반복하는 것이다.

 

 

만약에 물통의 물이 0 9 1으로 셋팅되어 있다면 현재 상황에서 물을 움직일 수 있는 가짓수를 따져 큐에 넣어주면 된다.

그렇다면 물을 움직일 수 있는 전체 상황이란 무엇일까? 말 그대로 3C2라고 생각하면 된다. 총 6가지 상황이 나올 수 있다.

 

A->B / A->C / B->C

B->A / C->A / C->B

 

그럼 (0, 9, 1) 상황에서 다음과 같은 6가지 사례가 도출될 수 있는 것이다.

 

그러나 위의 6가지 상황을 모두 큐에 넣는다면 중복 가짓수가 너무 많이 들어가게 된다.

이 때문에 3차원 visited를 이용하여 나왔던 [A][B][C] 조합을 체크하고 이미 나왔던 조합이면

1) 큐에 넣지 말거나

2) 큐에서 나왔을 때 visited 처리가 되어있는 조합이면 continue 한다. (난 이 방법)

 

큐에서 하나씩 빼면서 a가 0리터이면 정답 리스트에 넣어줄 것이다. 나는 정렬 방법이 빠른 Collection.sort를 이용할 것이기 때문에 ArrayList를 이용했다.

 

 

---

3. 전체 코드

---

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

class Main {
    static int maxA, maxB, maxC;
    static List<Integer> cList = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String ABC = br.readLine();
        StringTokenizer st = new StringTokenizer(ABC," ");

        maxA = Integer.parseInt(st.nextToken());
        maxB = Integer.parseInt(st.nextToken());
        maxC = Integer.parseInt(st.nextToken());

        PourBFS();

        Collections.sort(cList);

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<cList.size();i++){
            sb.append(cList.get(i)).append(" ");
        }

        System.out.println(sb);
        
    }

    public static void PourBFS(){
        Queue<Bottle> q = new LinkedList<>();
        boolean[][][] visited = new boolean[maxA+1][maxB+1][maxC+1];

        q.offer(new Bottle(0,0,maxC));

        while(!q.isEmpty()){
            Bottle cur = q.poll();
            
            //나왔던 케이스는 패스
            if(visited[cur.a][cur.b][cur.c]) continue;
            visited[cur.a][cur.b][cur.c] = true;

            //A = 0 이면 대상
            if(cur.a == 0) cList.add(cur.c);

            //지금 나온 보틀 케이스에서 할 수 있는 모든 상황을 다 해
            //A->B
            if(cur.a+cur.b>maxB){
                q.offer(new Bottle(cur.a+cur.b-maxB,maxB,cur.c));
            }else{
                q.offer(new Bottle(0,cur.a+cur.b,cur.c));
            }

            //A->C
            if(cur.a+cur.c>maxC){
                q.offer(new Bottle(cur.a+cur.c-maxC,cur.b,maxC));
            }else{
                q.offer(new Bottle(0,cur.b,cur.a+cur.c));
            }

            //B->C
            if(cur.b+cur.c>maxC){
                q.offer(new Bottle(cur.a,cur.b+cur.c-maxC,maxC));
            }else{
                q.offer(new Bottle(cur.a,0,cur.b+cur.c));
            }

            //C->B
            if(cur.b+cur.c>maxB){
                q.offer(new Bottle(cur.a,maxB,cur.b+cur.c-maxB));
            }else{
                q.offer(new Bottle(cur.a,cur.b+cur.c,0));
            }
            
            //C->A
            if(cur.a+cur.c>maxA){
                q.offer(new Bottle(maxA,cur.b,cur.a+cur.c-maxA));
            }else{
                q.offer(new Bottle(cur.a+cur.c,cur.b,0));
            }
            
            //B->A
            if(cur.a+cur.b>maxA){
                q.offer(new Bottle(maxA,cur.a+cur.b-maxA,cur.c));
            }else{
                q.offer(new Bottle(cur.a+cur.b,0,cur.c));
            }
        }
    }

    public static class Bottle{
        int a;
        int b;
        int c;
        public Bottle(int a, int b, int c){
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}