백준 2251 (물통) - java

 

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

2251번: 물통

* 크게 2가지 경우로 나눠볼 수 있다. A -> B의 경우를 생각해보자면 A 물통에 있는 모든 물을 B에 따를 수 있는 경우 , B의 물통이 그 전에 가득차 일부만 따르는 경우 

* 각 물통마다 2개의 물통에 따를 수 있기 때문에 6가지 경우의 수를 계산하여 BFS를 진행하면 된다.

* 참고로 HashSet에 결과를 저장하는 경우 정렬이 되는 것처럼 보이지만 기본적으로 정렬을 지원하지 않고 있다 ^^ !!!!

 

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

public class Main {
    static int maxA = 0;
    static int maxB = 0;
    static int maxC = 0;
    static boolean[][][] visit = new boolean[201][201][201];

   static HashSet<Integer> result = new HashSet<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine()," ");

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

        bfs();

        ArrayList<Integer> change = new ArrayList<>(result);
        Collections.sort(change);
        for (Integer integer : change) {
            System.out.print(integer+" ");
        } // 결과값을 정렬하기 위해 리스트로 변환 후 정렬
        br.close();
    }

    static void bfs()
    {
        Queue<bottle> q = new LinkedList<>();
        bottle start = new bottle(0,0,maxC);
        visit[0][0][maxC] = true;
        q.add(start);

        while(!q.isEmpty())
        {
            bottle cur = q.poll();
            if(cur.a==0)
            {
                result.add(cur.c);
            }

            // 가능한 경우의 수
            /*  붇는 쪽을 다 붇는 경우
                받는 쪽이 먼저 다 차서 다 못 붇는 경우
            * */
            if(cur.a!=0)
            {
               // a -> b
               int na = cur.a+cur.b;
               int ra = cur.a - (maxB - cur.b);
               if(na<=maxB&&!visit[0][na][cur.c]) // 전부 따를 수 있는 경우
               {
                   visit[0][na][cur.c] = true;
                   q.add(new bottle(0,na,cur.c));
               }

               else if(na>maxB&&!visit[ra][maxB][cur.c]) // 물통이 가득차 일부만 부어야 하는 경우
               {
                   visit[ra][maxB][cur.c] = true;
                   q.add(new bottle(ra,maxB, cur.c));
               }
               // a -> c

                na = cur.a+cur.c;
                ra = cur.a - (maxC - cur.c);
                if(na<=maxC&&!visit[0][cur.b][na])
                {
                    visit[0][cur.b][na] = true;
                    q.add(new bottle(0,cur.b,na));
                }

                else if(na>maxC&&!visit[ra][cur.b][maxC])
                {
                    visit[ra][cur.b][maxC] = true;
                    q.add(new bottle(ra,cur.b, maxC));
                }
            }

            if(cur.b!=0)
            {
                // b -> a
                int nb = cur.a+cur.b;
                int rb = cur.b - (maxA - cur.a);
                if(nb<=maxA&&!visit[nb][0][cur.c])
                {
                    visit[nb][0][cur.c] = true;
                    q.add(new bottle(nb,0,cur.c));
                }

                else if(nb>maxA&&!visit[maxA][rb][cur.c])
                {
                    visit[maxA][rb][cur.c] = true;
                    q.add(new bottle(maxA,rb, cur.c));
                }
                // b -> c

                nb = cur.b+cur.c;
                rb = cur.b - (maxC - cur.c);
                if(nb<=maxC&&!visit[cur.a][0][nb])
                {
                    visit[cur.a][0][nb] = true;
                    q.add(new bottle(cur.a,0,nb));
                }

                else if(nb>maxC&&!visit[cur.a][rb][maxC])
                {
                    visit[cur.a][rb][maxC] = true;
                    q.add(new bottle(cur.a,rb, maxC));
                }
            }

            if(cur.c!=0)
            {
                // c -> a
                int nc = cur.a+cur.c;
                int rc = cur.c - (maxA - cur.a);
                if(nc<=maxA&&!visit[nc][cur.b][0])
                {
                    visit[nc][cur.b][0] = true;
                    q.add(new bottle(nc,cur.b,0));
                }

                else if(nc>maxA&&!visit[maxA][cur.b][rc])
                {
                    visit[maxA][cur.b][rc] = true;
                    q.add(new bottle(maxA,cur.b, rc));
                }

                // c -> b
                nc = cur.c+cur.b;
                rc = cur.c - (maxB - cur.b);

                if(nc<=maxB&&!visit[cur.a][nc][0])
                {
                    visit[cur.a][nc][0] = true;
                    q.add(new bottle(cur.a,nc,0));
                }

                else if(nc>maxB&&!visit[cur.a][maxB][rc])
                {
                    visit[cur.a][maxB][rc] = true;
                    q.add(new bottle(cur.a,maxB, rc));
                }
            }
        }
    }
    // 물을 부울때는 한쪽으로만 붇는다 어느 한 쪽이 다 바닥 낼때까지
}
class bottle
{
    int a;
    int b;
    int c;

    bottle(int a,int b,int c)
    {
        this.a = a;
        this.b = b;
        this.c = c;
    }

}