[백준알고리즘 -2251] 물통 -java(BFS)

경우의 수가 200 * 200* 200 으로 크지 않기 때문에 완전 탐색이 가능하다. 

상태 저장을 위한 배열은 이차원 배열로 선언하였다. 

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

class Water{
	Water(int a, int b){
		this.a=a;
		this.b=b;
	}
	int a;
	int b;
}
class Main{
       public static void main(String[] args) throws IOException {
    	   Scanner scan=new Scanner(System.in);
    	   int a=scan.nextInt();//A용량
    	   int b=scan.nextInt();//B용량
    	   int C=scan.nextInt();//C용량 -> 총 물의 합

	   Queue queue=new LinkedList<>();
	   queue.add(new Water(0,0));
	   List arr=new ArrayList<>();
	   boolean[][] check=new boolean[a+1][b+1];
	   check[0][0]=true;
	   
	   while(!queue.isEmpty()) {
		   Water water=queue.poll();
		   int x=water.a;
		   int y=water.b;
		   int c=C-x-y;
	           if(x==0) {
			   arr.add(c);
		   }
		   
		   //x -> y,x
		   if(x>0) {
			   //x->y 
			   int avail=x+y <=b ? x : b-y;//옮길수있는 물의양
			   if(check[x-avail][y+avail]!=true)
			   {
				   queue.add(new Water(x-avail,y+avail));
				   check[x-avail][y+avail]=true;
			   }
			   //x->c , C보다 클 일은 없음
			   if(check[0][C-x-c]!=true) {
				   queue.add(new Water(0,C-x-c));
				   check[0][C-x-c]=true;
			   }
		   }
		  
		   //y->x,c
		   if(y>0) {
			   //y->x
			   int avail= x+y <= a ? y : a-x;
			   if(check[x+avail][y-avail]!=true)
			   {
				   queue.add(new Water(x+avail,y-avail));
				   check[x+avail][y-avail]=true;
			   }
			   //y->c
			   if(check[x][0]!=true) {
				   queue.add(new Water(x,0));
				   check[x][0]=true;
			   }
		   }
		   
		   //c -> x,y
		   if(c>0) {
			   //c->x
			   int avail= c+x <=a ? c : a-x;
			   if(check[x+avail][C-x-c]!=true) {
				   queue.add(new Water(x+avail,C-x-c));
				   check[x+avail][C-x-c]=true;
			   }
			   
			   //c->y
			   avail= c+y <=b ? c : b-y;
			   if(check[x][y+avail]!=true) {
				   queue.add(new Water(x,y+avail));
				   check[x][y+avail]=true;
			   }
		   }


	   }

	  Collections.sort(arr);
	   for(int i=0; i<arr.size(); i++)
		   System.out.print(arr.get(i)+" ");

bfs 문제 다 풀고나서 저 중복코드들 정리하는 방법좀 생각해봐야겠다. 보기 너무 길다 ㅠ___ㅠ