백준 2251 물통 : bfs와 브루트포스 - c++

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

2251번: 물통

총 6가지 경우의 수에 대해서 전부 bfs.

각각의 물 담긴 상태가 이미 저장되어 있으면 넘기고.

세가지 상태를 전부 저장하는 경우는 처음이었다.(pair 안의 pair을 활용해서 상태를 저장할 수 있다.)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int A,B,C;
bool visited[201][201][201];
 
vector<int> bfs(void){
    queue<pair<pair<int,int>,int>> q;
    q.push(make_pair(make_pair(0,0),C));
    vector<int> 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<int> result = bfs();
    sort(result.begin(),result.end());
    for (int i = 0; i < result.size(); i++)
        cout << result[i]<< " ";
 
}