[2251번] 물통

[문제] 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

[예제입력]

8 9 10

[예제출력]

1 2 8 9 10

[풀이를 위한 개념]

http://twoearth.tistory.com/3?category=809135 (숨바꼭질) 문제에서 사용하는 BFS를 참조하시길 바랍니다.

BFS 는 다음과 같은 문제에 사용되는 알고리즘입니다.

1. 최소 상태의 개수가 충분히 작다.

2. 최소비용을 구하는 문제

3. 이동간극(비용)이 1로 동일해야 한다.

처음 이 문제를 접했을 때, BFS를 이용한다는 것을 떠올리기는 어렵습니다.

일단 BFS를 사용하는 문제의 유형 (위 3가지)과 충분히 만족하는지 판별하기 어렵기 때문입니다.

일단 최소 상태의 개수는, 물통 3개에 물이 들어갈 수 있는 가짓수가 200개씩 있으므로 200x200x200 = 8,000,000개로 충분히 작습니다.

그리고 물을 이동시킬 때, 들어 있는 물을 모두 비워야 하므로 이동비용 또한 1로 동일하다고 생각할 수 있습니다. (수행이 한번만 일어나므로)

사실 최소비용을 구하는 문제가 아니기 때문에 BFS를 떠올리기 힘든데, 문제를 조금 변형해서 C 물통에 들어 있는 물이 주어 질 때, 최소 몇번 물을 이동시켜야 하는가의 문제로 생각해보면 이 문제와 비슷하다는 것을 알 수 있습니다.

즉, 이 문제 또한 물이 담겨있는 모든 경우의 수를 탐색해야 하므로 BFS를 사용하는 것이 적합합니다.

이 또한 queue를 이용해서 풀어야 하는데, 이 경우에는 물통에 들어있는 물의 용량의 조합을 알아봐야 하므로 3가지의 데이터를  queue에 저장해야 합니다. 하지만 물의 양이 정해져 있으므로 두가지 데이터를 넣고 다니는 queue를 사용하면 됩니다.

두가지 데이터가 쌍을 이루어 queue를 형성할 때, 

queue< pair<int, int> > q;

로 선언 할 수 있습니다.

그리고 쌍으로 데이터를 추가할 때는

q.push(make_pair(data1, data2));

로 가능합니다.

q.pop();

을 하게 되면 front에 있던 데이터 쌍으로 제거되게 됩니다.

[풀이과정]

위에서 상태의 개수는 8,000,000개라고 했지만 처음 주어지는 물의 양은 변하지 않으므로 상태의 개수를 조금 줄일 수 있겠습니다. C물통에 물이 들어가므로 A와 B만 주어진다면 C의 값은 자동으로 정해지게 되죠.

그러므로 상태의 개수는 40,000개로 줄어들고 문제 풀이도 수월해질 것 같습니다.

물을 담는 경우는 A-B, A-C, B-A, B-C, C-A, C-B 총 6가지이므로 매 데이터마다 6갈래로 나눠집니다.

물은 넘치게끔 담을 수 없지만 무조건 부어야 합니다.(부어야하는 물통이 꽉 차있더라도 물을 반드시 붓는다고 생각합니다.)

그렇다면 담고자 하는 물통이 붓는 물을 모두 담을 수 있는 경우와 넘치는 경우, 두가지로 나눌 수 있습니다.

Step 1. 한번 물을 옮기는 과정 속에서 물이 넘쳤을 때 각 물통에 남아 있는 물의 양, 넘치지 않았을 때 각 물통에 남아 있는 물의 양 두가지로 나눠서 계산합니다.

Step 2. Step 1의 계산 과정을 여섯가지 경우의 수로 모두 표현합니다.

[그림1] 옮겨담을 물통의 용량이 크던 작던 일단 다 옮긴 후 넘치는 경우에만 남은 걸 다시 가져오면 코드가 더 줄어든다.

[그림1]과 같이 물을 옮겼을 때, 남은 물의 양과 옮긴 물의 양을 정할 수 있습니다.

그리고 매 과정마다 물통 C에 들어 있는 물의 양을 체크해주고 저장합니다.

각 물통에 들어 있는 물의 양의 조합이 처음보는 조합일 때만 시행해야 무한루프를 막을 수 있습니다. (visited[] 배열 사용)

[풀이과정]

#include<iostream>
#include<queue>
 
 
 
using namespace std;
 
int result[201];        //C에 들어 있는 물의 양은 1로 체크한다.
int visited[201][201];    //A,B 물통에 들어 있는 물의 양으로 방문여부를 판단
 
 
int main()
{
 
    int a;
    int b;
    int c;
 
    cin >> a >> b >> c;
 
    int x,y,z;            //물의 양
    int nx,ny,nz;        //6가지 계산에서 초기화를 위한 물의 양
 
    queue< pair<int, int> > q;        //쌍으로 queue 선언
    result[c] = 1;                    //C물통에 처음 들어 있는 물의 양 체크
    q.push(make_pair(0,0));            //처음 A,B 물통은 비어 있음
 
    while(!q.empty())
    {
        x = q.front().first;        //쌍으로 선언되어 있는 queue에서 첫번째 데이터가 A 
        y = q.front().second;        //쌍으로 선언되어 있는 queue에서 두번째 데이터가 B
        z = c - x - y;
        q.pop();
 
        //현재 물의 양
        nx = x;
        ny = y;
        nz = z;
 
        //x에서 y로
 
        ny += nx;
        nx = 0;                //x에 있던 물 다 넣었기 때문에 0
        if(ny >= b)            //용량을 초과할 경우
        {
            nx = ny - b;    //(용량을 초과할 경우) x를 전부 붓고나서 y에서 용량B를 빼준 값을 다시 x가 가져온다.
            ny = b;            // y는 꽉차게 된다.
        }
        if(visited[nx][ny] != 1)        //방문하지 않은 node일 때, push 해준다.
        {
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
            if(nx == 0)
            {
                result[nz] = 1;
            }
        }
 
        //현재 물의 양
        nx = x;
        ny = y;
        nz = z;
 
        //x에서 z로
 
        nz += nx;
        nx = 0;
        if(nz >= c)
        {
            nx = nz - c;
            nz = c;
        }
        if(visited[nx][ny] != 1)
        {
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
            if(nx == 0)
            {
                result[nz] = 1;
            }
        }
 
        //현재 물의 양
        nx = x;
        ny = y;
        nz = z;
 
        //y에서 x로
 
        nx += ny;
        ny = 0;
        if(nx >= a)
        {
            ny = nx - a;
            nx = a;
        }
        if(visited[nx][ny] != 1)
        {
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
            if(nx == 0)
            {
                result[nz] = 1;
            }
        }
 
        //현재 물의 양
        nx = x;
        ny = y;
        nz = z;
 
        //y에서 z로
 
        nz += ny;
        ny = 0;
        if(nz >= c)
        {
            ny = nz - c;
            nz = c;
        }
        if(visited[nx][ny] != 1)
        {
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
            if(nx == 0)
            {
                result[nz] = 1;
            }
        }
 
        //현재 물의 양
        nx = x;
        ny = y;
        nz = z;
 
        //z에서 x로
 
        nx += nz;
        nz = 0;
        if(nx >= a)
        {
            nz = nx - a;
            nx = a;
        }
        if(visited[nx][ny] != 1)
        {
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
            if(nx == 0)
            {
                result[nz] = 1;
            }
        }
 
        //현재 물의 양
        nx = x;
        ny = y;
        nz = z;
 
        //z에서 y로
 
        ny += nz;
        nz = 0;
        if(ny >= b)
        {
            nz = ny - b;
            ny = b;
        }
        if(visited[nx][ny] != 1)
        {
            visited[nx][ny] = 1;
            q.push(make_pair(nx,ny));
            if(nx == 0)
            {
                result[nz] = 1;
            }
        }
 
    }
 
    for(int i=0; i<=c; i++)
    {
        if(result[i] == 1)
        {
            cout<<i<<' ';
        }
    }
    cout << endl;
    return 0;
 
}

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다