[BFS] 2251번 물통

2251번 물통

 

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

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

8 9 10

 

예제 출력

1 2 8 9 10

 

 

해결방법

BFS 탐색을 통해 정답의 경우를 모두 찾는 문제이다

 

이 문제는 사실 1달 전에 풀다가 코드가 너무 난잡해서 중간에 포기했었다

마음을 가다듬고 다시 한땀x2 풀어봤다

 

먼저 물통은 총 3개이다

따라서 3개의 물통의 상태를 저장하기 위해 구조체를 사용한다

struct bucket {
    int a,b,c;
    
    bucket() {}
    bucket(int _a,int _b,int _c) : a(_a),b(_b),c(_c) {}
};

 

이제 물통 간에 물을 이동시켜야한다

 

만약 A 물통에서 B 물통으로 이동한다고 가정해보자

먼저 A 물통은 비어있으면 안된다

또한 물을 붓는 걸 멈추는 조건은 물통을 쏟아 부었을 때, A물통 이 바닥나거나 B물통 이 가득차는 경우다

 

A 물통이 바닥나는 경우

• A : 0
• B : 현재 A 물통의 양 + 현재 B 물통의 양

// A is Empty
int sum = nowA + nowB;
if(nowA+nowB <= maxB){
    if(!visited[0][sum][nowC]){
        q.push(bucket(0,sum,nowC));
        visited[0][sum][nowC] = true;
    }
}

 

B 물통이 가득차는 경우

• A : 현재 A 물통의 양 + 현재 B 물통의 양 - B 물통의 최대값
• B : B 물통의 최대값

// B is Full
else{
    int sub = sum - maxB;
    if(!visited[sub][maxB][nowC]){
        q.push(bucket(sub,maxB,nowC));
        visited[sub][maxB][nowC] = true;
    }
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 201
#define INF 987654321
using namespace std;

struct bucket {
    int a,b,c;
    
    bucket() {}
    bucket(int _a,int _b,int _c) : a(_a),b(_b),c(_c) {}
};

int maxA,maxB,maxC;
bool visited[MAX][MAX][MAX];

set<int> ans;

void bfs(){
    queue<bucket> q;
    q.push(bucket(0,0,maxC));
    visited[0][0][maxC] = true;
    
    while(!q.empty()){
        int nowA = q.front().a;
        int nowB = q.front().b;
        int nowC = q.front().c;
        q.pop();
        
        // 정답을 찾은 경우
        // A is Empty, C ?
        if(nowA == 0){
            ans.insert(nowC);
        }
        
        /***************[ A ]***************/
        if(nowA != 0){
            /*****[ A → B ]*****/
            // A is Empty
            int sum = nowA + nowB;
            if(nowA+nowB <= maxB){
                if(!visited[0][sum][nowC]){
                    q.push(bucket(0,sum,nowC));
                    visited[0][sum][nowC] = true;
                }
            }
            // B is Full
            else{
                int sub = sum - maxB;
                if(!visited[sub][maxB][nowC]){
                    q.push(bucket(sub,maxB,nowC));
                    visited[sub][maxB][nowC] = true;
                }
            }
            
            /*****[ A → C ]*****/
            // A is Empty
            sum = nowA + nowC;
            if(nowA+nowC <= maxC){
                if(!visited[0][nowB][sum]){
                    q.push(bucket(0,nowB,sum));
                    visited[0][nowB][sum] = true;
                }
            }
            // C is Full
            else{
                int sub = sum - maxC;
                if(!visited[sub][nowB][maxC]){
                    q.push(bucket(sub,nowB,maxC));
                    visited[sub][nowB][maxC] = true;
                }
            }
        }
        
        /***************[ B ]***************/
        if(nowB != 0){
            /*****[ B → A ]*****/
            // B is Empty
            int sum = nowB + nowA;
            if(nowB+nowA <= maxA){
                if(!visited[sum][0][nowC]){
                    q.push(bucket(sum,0,nowC));
                    visited[sum][0][nowC] = true;
                }
            }
            // A is Full
            else{
                int sub = sum - maxA;
                if(!visited[maxA][sub][nowC]){
                    q.push(bucket(maxA,sub,nowC));
                    visited[maxA][sub][nowC] = true;
                }
            }
            
            /*****[ B → C ]*****/
            // B is Empty
            sum = nowB + nowC;
            if(nowB+nowC <= maxC){
                if(!visited[nowA][0][sum]){
                    q.push(bucket(nowA,0,sum));
                    visited[nowA][0][sum] = true;
                }
            }
            // C is Full
            else{
                int sub = sum - maxC;
                if(!visited[nowA][sub][maxC]){
                    q.push(bucket(nowA,sub,maxC));
                    visited[nowA][sub][maxC] = true;
                }
            }
        }
        
        /***************[ C ]***************/
        if(nowC != 0){
            /*****[ C → A ]*****/
            // C is Empty
            int sum = nowC + nowA;
            if(nowC+nowA <= maxA){
                if(!visited[sum][nowB][0]){
                    q.push(bucket(sum,nowB,0));
                    visited[sum][nowB][0] = true;
                }
            }
            // A is Full
            else{
                int sub = sum - maxA;
                if(!visited[maxA][nowB][sub]){
                    q.push(bucket(maxA,nowB,sub));
                    visited[maxA][nowB][sub] = true;
                }
            }
            
            /*****[ C → B ]*****/
            // C is Empty
            sum = nowC + nowB;
            if(nowC+nowB <= maxB){
                if(!visited[nowA][sum][0]){
                    q.push(bucket(nowA,sum,0));
                    visited[nowA][sum][0] = true;
                }
            }
            // B is Full
            else{
                int sub = sum - maxB;
                if(!visited[nowA][maxB][sub]){
                    q.push(bucket(nowA,maxB,sub));
                    visited[nowA][maxB][sub] = true;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> maxA >> maxB >> maxC;
    
    memset(visited, false, sizeof(visited));
    bfs();
    
    // 정답 출력
    for(auto it=ans.begin(); it!=ans.end(); ++it){
        cout << *it << " ";
    }
    cout << "\n";
    
    return 0;
}