[백준 2251 - C++] 물통 : BFS

www.acmicpc.net/problem/2251

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

 

풀이

솔직히 말하면 이 문제의 알고리즘 분류가 BFS인걸 몰랐다면 절대 못풀었을 것 같다.

bfs는 항상 map으로 생각한 나 자신 반성해...

 

이 문제를 보고 조건 확인 이 필요하다는 생각이 든건 위와 같다.

물통의 물을 옮기는 것은 저렇게 6가지 이동 방향이 가능하고 각각의 이동에 있어서 그 물의 양은 또 두가지 가 가능하다.

우선 물을 옮길 수 있으려면 채워지는 쪽이 가득 차있는 상태가 아니어야하고, 옮기는 쪽이 비어있는 상태가 아니어야 한다.

옮기는 물의 양은 채워지는 쪽의 남은 공간이 옮기는 쪽의 물의 양 보다 많은 경우와 적은 경우가 있다. 이것까지 조건문으로 구현한다면, 너무 코드가 지저분해 질 거라고 생각이 들어서 줄이는 방법이 뭐가 있을까하고 생각해보았는데,

옮기는 물의 양의 경우엔 if문으로 조건을 확인할 필요없다는 생각이 들었다. 채워지는 쪽의 남은 공간과 옮기는 쪽의 물의 양 중 더 작은 양만큼만 이동가능 하기 때문이다. 따라서 그냥 둘중 min값을 이동 양으로 하여 큐에 push해주는 쪽으로 생각하였다.

 

또한 방문 여부 확인은 3차원 배열을 선언해서 각각의 A, B, C 조합을 모두 고려하는 방식을 택했는데, 더 효율적인 방법이 있을 수 있지않나 라는 생각이 들었다.

 

그리고 가능한 c의 양을 중복없이 오름차순으로 저장하고 싶어서 set을 이용하였다. 진심 편하다 이거

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <set>

using namespace std;

queue<pair<pair<int, int>, int>> check;
int visited[201][201][201];
set<int> can_c;

int main (void){
    int a, b, c;
    int p_a, p_b, p_c;
    int n_a, n_b, n_c;
    int move;
    set<int>::iterator it;
    
    scanf("%d %d %d", &a, &b, &c);
    
    check.push(make_pair(make_pair(0, 0),c));
    can_c.insert(c);
    
    while(!check.empty()){
        p_a = check.front().first.first;
        p_b = check.front().first.second;
        p_c = check.front().second;
        check.pop();
        
        if(visited[p_a][p_b][p_c])
            continue;
        
        visited[p_a][p_b][p_c] = 1;
        
       // printf("%d %d %d\n", p_a, p_b, p_c);
        
        if(p_a!=0){
            if(p_b!=b){      //A->B
                move = min(p_a, b - p_b);
                n_a = p_a - move;
                n_b = p_b + move;
                n_c = p_c;
                check.push(make_pair(make_pair(n_a, n_b),n_c));
                if(n_a == 0)
                    can_c.insert(n_c);
            }
            if(p_c!=c){     //A->C
                move = min(p_a, c - p_c);
                n_a = p_a - move;
                n_b = p_b;
                n_c = p_c + move;
                check.push(make_pair(make_pair(n_a, n_b),n_c));
                if(n_a == 0)
                    can_c.insert(n_c);
            }
        }
        
        if(p_b!=0){
            if(p_a!=a){      //B->A
                move = min(p_b, a - p_a);
                n_a = p_a + move;
                n_b = p_b - move;
                n_c = p_c;
                check.push(make_pair(make_pair(n_a, n_b),n_c));
                if(n_a == 0)
                    can_c.insert(n_c);
           
            }
            if(p_c!=c){     //B->C
                move = min(p_b, c - p_c);
                n_a = p_a;
                n_b = p_b - move;
                n_c = p_c + move;
                check.push(make_pair(make_pair(n_a, n_b),n_c));
                if(n_a == 0)
                    can_c.insert(n_c);
            }
        }
        
        if(p_c!=0){
            if(p_a!=a){      //C->A
                move = min(p_c, a - p_a);
                n_a = p_a + move;
                n_b = p_b;
                n_c = p_c - move;
                check.push(make_pair(make_pair(n_a, n_b),n_c));
                if(n_a == 0)
                    can_c.insert(n_c);
           
            }
            if(p_b!=b){     //C->B
                move = min(p_c, b - p_b);
                n_a = p_a;
                n_b = p_b + move;
                n_c = p_c - move;
                check.push(make_pair(make_pair(n_a, n_b),n_c));
                if(n_a == 0)
                    can_c.insert(n_c);
            }
        }
    }
    
    for (it = can_c.begin(); it != can_c.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
}