물통

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

2251번: 물통

 

숨바꼭질, DSLR 문제와 유사하다.

각 단계를 노드라고 생각하는 것.

물을 옮기는 방법은 6가지 있다.

그에 따른 send, receive 배열을 만들어서

BFS를 돌리자.

 

visited 배열은 삼차원이 필요가 없다.

물의 양은 정해져 있기 때문!

이차원 배열을 만들고

C = now[2] - A - B 하면 됨.

 

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
// 물통 번호 0, 1, 2
int send[] = { 0, 0, 1, 1, 2, 2 };
int receive[] = { 1, 2, 0, 2, 0, 1 };
 
// 3차원 배열을 쓰는 게 아니라
// A, B의 용량이 있으면 C의 용량이 고정
bool visited[201][201];
bool answer[201];
int now[3];
 
void BFS()
{
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    visited[0][0] = true;
    // 처음에 A는 비어있으니
    answer[now[2]] = true;
 
    while (!q.empty())
    {
        int A = q.front().first;
        int B = q.front().second;
        int C = now[2] - A - B;
        q.pop();
 
        for (int k = 0; k < 6; k++)
        {
            int next[] = { A, B, C };
            next[receive[k]] += next[send[k]];
            next[send[k]] = 0;
 
            // 대상 물통의 용량ㅂ다 물이 많을 때
            if (next[receive[k]] > now[receive[k]])
            {
                // 초과하는 만큼 다시 이전 물통에 넣음
                next[send[k]] = next[receive[k]] - now[receive[k]];
                // 대상 물통은 최대로 채움
                next[receive[k]] = now[receive[k]];
            }
 
            if (!visited[next[0]][next[1]])
            {
                visited[next[0]][next[1]] = true;
                q.push(make_pair(next[0], next[1]));
 
                if (next[0] == 0)
                    answer[next[2]] = true;
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> now[0] >> now[1] >> now[2];
    BFS();
 
    for (int i = 0; i <= now[2]; i++)
    {
        if (answer[i])
            cout << i << ' ';
    }
 
    return 0;
}