[백준 2251] 물통

 물통의 갯수는 세개이고 물통의 크기는 1부터 200까지이다.

 이때 물통의 갯수가 세개이기 때문에

 모든 경우를 고려한 BFS 알고리즘을 사용하여

 A 물통이 비어있을 때, C의 물통에 담겨 있는 물의 양을 출력하면 된다.

 모든 경우라고 해봤자.  총 6가지이다

1. A -> B

2. A -> C

3. B -> A

4. B -> C

5. C -> A

6. C -> B

( 각각의 모든 경우는, 옮기려는 물들이 옮기려는 곳의 최대 용량보다 많은지 검사를 해야한다.)

음수가 나오므로 불 필요한 연산을 하지 않기 위해서

 1. 임의로 만든 water 구조를 사용하여, 저장 및 사용이 편리하도록 Queue<water>을 사용하였다.

 2. 방문 여부를 확인 하기 위해서 bool visit[][][]를 작성하였다.

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

문제

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

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

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

소스코드

#include<iostream>
#include<queue>
#include<set>
 
using namespace std;
 
bool visit[201][201][201];        // 방문 여부 확인 
 
struct water {
    int A, B, C;                    // 현재 담긴 물
};
 
int main(void) {
    int A, B, C;                // 물통의 용량 크기 
    cin >> A >> B >> C;            // 물통의 용량
    set<int> ans;                // 정답을 담을 컨테이너 
    queue<water> q;                // water 구조를 사용한 queue 컨테이너 
    q.push({ 0,0,C });            // queue에 초기 값을 삽입한다. 
 
    while (!q.empty()) {
        int curr_A = q.front().A;        // 현재 A에 담겨 있는 물의 양 
        int curr_B = q.front().B;        // 현재 B에 담겨 있는 물의 양 
        int curr_C = q.front().C;        // 현재 C에 담겨 있는 물의 양 
        q.pop();
        
        if (visit[curr_A][curr_B][curr_C])        // 이미 방문한 경우 
            continue;
        
        // 첫 방문 
        visit[curr_A][curr_B][curr_C] = true;
 
        // A의 물이 0일때 
        if (curr_A == 0) {
            ans.insert(curr_C);
        }
        // case 1    a -> b
        if (curr_A + curr_B > B)
            q.push({ curr_A + curr_B - B, B, curr_C });
        else
            q.push({ 0, curr_A + curr_B, curr_C });
 
        // case 2     a -> c
        if (curr_A + curr_C > C)
            q.push({ curr_A + curr_C - C, curr_B, C });
        else
            q.push({ 0, curr_B, curr_A + curr_C });
            
        // case 3    b -> a
        if (curr_A + curr_B > A)
            q.push({ A, curr_A + curr_B - A, curr_C });
        else
            q.push({ curr_A + curr_B, 0, curr_C });
 
        // case 4    b -> c
        if (curr_B + curr_C > C)
            q.push({ curr_A, curr_B + curr_C - C , C });
        else
            q.push({ curr_A, 0, curr_B + curr_C });
            
        // case 5    c -> b
        if (curr_B + curr_C > B)
            q.push({ curr_A, B, curr_B + curr_C - B });    
        else
            q.push({ curr_A, curr_B + curr_C, 0 });     
 
        // case 6    c -> a
        if (curr_A + curr_C > A)
            q.push({ A, curr_B, curr_A + curr_C - A });
        else
            q.push({ curr_A + curr_C, curr_B, 0 });
 
    }
 
    // 정답 출력 
    set<int>::iterator iter;
    for (iter = ans.begin(); iter != ans.end(); iter++)
        cout << *iter << ' ';
        
    // 종료 
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.