백준 2251번 물통

문제 링크입니다: https://www.acmicpc.net/problem/2251

처음에는 A 물통과 B 물통은 비어있고 C 물통은 가득 찬 상태에서 시작합니다.

한 물통이 비거나, 다른 물통이 가득 찰 때까지 물을 부을 수 있으므로 아래와 같이 두 가지 경우의 수를 고려해줘야 합니다.

1. 비우는 물통과 채우는 물통의 합이 채우는 물통의 한계보다 클 경우, 비우는 물통은 완전히 비지 않습니다.

2. 비우는 물통과 채우는 물통의 합이 채우는 물통의 한계보다 같거나 작을 경우 비우는 물통은 완전히 빕니다.

위 두 조건을 고려했다면, BFS(Breadth First Search) 알고리즘을 적용하여 A 물통이 비었을 때 C 물통이 가질 수 있는 물의 높이를 정렬하여 순차적으로 출력해주면 AC 처리를 받을 수 있습니다!

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 200 + 1;

 

int A, B, C;

bool cache[MAX][MAX][MAX];

 

vector<int> BFS(void)

{

        queue < pair<pair<int, int>, int>> q; //A, B, C

        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 (cache[a][b][c])

                         continue;

 

                 cache[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 + b - 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] << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~