백준 2251 물통 - 세 쌍 벡터를 이용한 bfs

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

2251번: 물통

이 문제를 풀기 위해서는 물통 a,b,c를 각각 한 쌍으로 만든 다음에, 세쌍 동시에 bfs를 진행해야 한다. 

a b c 각각 물통에 담긴 물의 양을 저장해가면서 bfs를 진행할 것.

 

 

 

#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
int A,B,C;
bool visited[201][201][201];

vector bfs(void){
    queue<pair<pair<int,int>,int>> q;
    q.push(make_pair(make_pair(0,0),C));
    vector result;

    while(!q.empty()){
        int a = q.front().first.first;
        int b = q.front().first.second;
        int c = q.front().second;
        q.pop();

        if(visited[a][b][c]){
            continue;
        }
        visited[a][b][c]=true;
        if(a==0)
            result.push_back(c);

        //a->b
        if (a + b > B) //안넘치는 범위에서 따라야함
            q.push(make_pair(make_pair(a + b - B, B), c));
        else //걍따라도 됨
            q.push(make_pair(make_pair(0, a + b), c));



        //a->c
        if (a + c > C)
            q.push(make_pair(make_pair(a + c - C, b), C));
        else
            q.push(make_pair(make_pair(0, b), a + c));



        //b->a
        if (b + a > A)
            q.push(make_pair(make_pair(A, b + a - A), c));
        else
            q.push(make_pair(make_pair(b + a, 0), c));



        //b->c
        if (b + c > C)
            q.push(make_pair(make_pair(a, b + c - C), C));
        else
            q.push(make_pair(make_pair(a, 0), b + c));



        //c->a
        if (c + a > A)
            q.push(make_pair(make_pair(A, b), c + a - A));
        else
            q.push(make_pair(make_pair(c + a, b), 0));



        //c->b
        if (c + b > B)
            q.push(make_pair(make_pair(a, B), c + b - B));
        else
            q.push(make_pair(make_pair(a, c + b), 0));
    }
    return result;
}


int main(void){
    cin>>A>>B>>C;
    vector result = bfs();
    sort(result.begin(),result.end());
    for (int i = 0; i < result.size(); i++)
        cout << result[i]<< " ";

}