[백준] 2251번 물통문제 BFS로 풀어보기

www.acmicpc.net/problem/2251

2251번: 물통

더 자세한 문제의 제한은 위의 링크에 들어가서 확인해보자

 

---

C++로 푼 풀이의 경우 

programmingstory.com/bbs/board.php?bo_table=100joon&wr_id=91

Programming Story

위 글을 참고하기 바란다. 잘 설명되어 있는 것 같다.

---

나는 자바로 이 문제를 풀어보겠다. 알고리즘 자체는 위 글에 나와있는 내용을 참고해서 거의 유사하다. 자바 버전이 궁금한 사람은 내 풀이를 보고, C++ 버전이 궁금한 사람은 위 게시판에 나와있는 코드를 참고하면 좋을 것 같다.

 

이 물통 문제는 처음에 어떻게 풀까 고민을 하다가 위 풀이를 보고 BFS로 풀면 된다는 것을 알게 되었다.

 

물통 초기상태

물통의 총합이 변하지 않는다는 것이 문제에서 가장 중요한 열쇠이다. 그러면 물통 자체는 3개가 있지만 두개만 우리는 미지수로 두고 나머지 하나는 총합에서 빼는 식으로 구상하면 된다. 그리고 심지어 전체 합은 문제 시작 때 주어져있기 때문에 (2번 물통 양이 처음에는 sum이다) 매우 편하게 구할 수 있다.

 

그런 다음에 처음 물통 0과 물통 1은 0,0으로 시작하니 이들을 queue에 넣어주고 여기서부터 물통에 물을 옮겨담을 수 있는 모든 조합을 시도해보는 것이다. 

 

순열로 해도 되지만 이렇게 6개밖에 되지 않는 것은 그냥 배열로 from, to 해서 여섯가지를 모두 시도해보는 것이 간단하다. 

그리고 이 문제에서 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다고 했으므로 우선 다른 물통에 물을 다 부어놓고 이것이 용량을 초과하게 되면 다시 원래 물통에 넘친 만큼 부어준다는 식으로 구현을 하면 될 것 같다. 

그러면 비록 넘칠 때까지 부었어도 넘친 부분을 원상복구시켜주면서 물통이 가득찰 때까지만 부은 것이 되기 때문이다. 

 

그리고 제한이 200밖에 되지 않기 때문에 200까지 배열의 용량을 넉넉히 만들어 구해주면 된다.

 

Pair라는 class를 만들어도 되지만 나는 그것이 번거로워서 그냥 0번째 물통 값 넣어주고 1번째 물통 값 넣어주고 이런 식으로 구현했다. 전혀 문제 없는 방식이고 대신 queue에서 뺄 때도 두개를 다 빼주어야 한다.

 

import java.util.*;

public class Main{
    final static int to[]={0,0,1,1,2,2};
    final static int from[]={1,2,0,2,0,1};
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        int water[]=new int [3];
        for(int i=0; i<3; i++){
            water[i]=sc.nextInt();
        }
        int sum=water[2];
        boolean check[][]=new boolean[201][201];
        boolean ans[]=new boolean[201];
        Queue <Integer> q= new LinkedList<>();
        q.add(0);
        q.add(0);
        check[0][0]=true;
        ans[water[2]]=true;
        while(!q.isEmpty()){
            int cur[]=new int [3];
            cur[0]=q.remove();
            cur[1]=q.remove();
            cur[2]=sum-cur[0]-cur[1];
            for(int k=0; k<6; k++){
                int next[]={cur[0], cur[1], cur[2]};
                next[to[k]]+=next[from[k]];
                next[from[k]]=0;
                if (next[to[k]]>=water[to[k]]){
                    next[from[k]]=next[to[k]]-water[to[k]];
                    next[to[k]]=water[to[k]];
                }
                if (!check[next[0]][next[1]]){
                    check[next[0]][next[1]]=true;
                    q.add(next[0]);
                    q.add(next[1]);
                    if (next[0]==0){
                        ans[next[2]]=true;
                    }
                }
            }
        }
        for(int i=0; i<=water[2]; i++){
            if (ans[i]){
                  System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

여기서 check라는 배열은 0번째 물통 값, 1번째 물통 값의 조합이 예전에 나온 조합임을 확인하는 boolean 배열이고 ans 배열은 문제의 조건을 만족시키는지 확인하는 배열이다. 

 

이런식으로 구하면 문제에서 요구하는 조건은 ans 배열을 0부터 2번 물통 최대 값(sum)까지 따라가면서 true인 값을 적어주면 된다.