[BOJ] 2251 물통 C++

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

2251번: 물통

처음에 보고 이게 왜 그래프 이론인지 생각했다. '그냥 조건 몇 개 넣고 돌리면 되겠네!'라는 안일한 생각을 가지고 10분 만에 짜서 제출했지만 바로 뜨는 틀렸습니다...

 

한 20분 정도 혼자 끄적이다 결국 다른 분들의 풀이를 봤다. 역시 내가 넣은 조건에는 예외가 존재했다. 모든 조건을 넣는 것은 매우 힘들기 때문에 필수 조건을 넣어주고 BFS를 돌리면 됐다. 경우의 수를 구하는 문제를 BFS로 푸는 법이 익숙하지 않은 것 같다.

 

코드

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#define MAX 201

using namespace std;

int A,B,C;

vector<int> v;

bool check[MAX][MAX];

 

void bfs(){

    queue< pair<pair<int,int>,int > >q;

    q.push(make_pair(make_pair(0,0),C));

    while(!q.empty()){

        //물의 양 a,b,c

        int a=q.front().first.first;

        int b=q.front().first.second;

        int c=q.front().second;

        q.pop();

        //물의 양이 a,b였던 경우를 이미 방문했다면 pass

        if(check[a][b]) continue;

        check[a][b]=true;

        if(a==0) v.push_back(c);

        //a->b

        if(a+b<B){

            //A에서 B로 옮길 때, a와 b의 합이 물통 B의 용량보다 작을 경우 a+b 모두 B에 들어간다.

            q.push(make_pair(make_pair(0,a+b),c));

        }else{

            //a에서 b로 옮길 때, a와 b의 합이 물통 B의 용량보다 클 경우

            //물통 B에는 B만큼 물이 들어가고, A에는 a+b-B만큼이 남게 된다.

            q.push(make_pair(make_pair(a+b-B,B),c));

        }

        //위 개념을 반복하면 된다.

        //a->c

        if(a+c<C){

            q.push(make_pair(make_pair(0,b),a+c));

        }else{

            q.push(make_pair(make_pair(a+c-C,b),C));

        }

        //b->c

        if(b+c<C){

            q.push(make_pair(make_pair(a,0),b+c));

        }else{

            q.push(make_pair(make_pair(a,b+c-C),C));

        }

        //b->a

        if(a+b<A){

            q.push(make_pair(make_pair(a+b,0),c));

        }else{

            q.push(make_pair(make_pair(A,a+b-A),c));

        }

        //c->a

        if(a+c<A){

            q.push(make_pair(make_pair(a+c,b),0));

        }else{

            q.push(make_pair(make_pair(A,b),a+c-A));

        }

        //c->b

        if(b+c<B){

            q.push(make_pair(make_pair(a,b+c),0));

        }else{

            q.push(make_pair(make_pair(a,B),b+c-B));

        }

        

    }

}

 

int main(){

    cin>>A>>B>>C;

    bfs();

    sort(v.begin(),v.end());

    for(int i=0;i<v.size();i++) cout<<v[i]<<" ";

    return 0;

}

 

 

경우를 BFS로 구할 수 있다는 것을 꼭 명심하자.