물통 2251

문제

접근 방법

한번 표로 확인해보자.

0	0	10

시작 상태는 이렇다.

0	9	1
8	0	2

한번 돌고 나면 이럴 것이다.

8	1	1
1	9	0
0	0	10
0	8	2
8	2	0
0	0	10

이전에 나온 값과 겹치는 경우는 제외되겠지만 일단 존재할 것이다.
다음 경우에선 제외해줄 것이다.

0	1	9
1	0	9
2	8	0
0	2	8

한 지점을 잡고 좌우로 값을 탐색해주면 되는 느낌인 것을 알게 됐다. (겹치면 제외되니 많은 값이 목록에 오르진 않을 것이다.)

9	1	0
0	8	2
2	0	8

예제 답에 해당하는 값들이 다 나왔다.
모든 경우를 확인했기에 더 이상 돌 수가 없다.

물의 총량은 정해져 있기에 2개의 경우만 들고 있어도 된다. (2개로 나머지를 구할 수 있다.)

코드

#include <iostream>
#include <set>
#include <queue>
#include <vector>
using namespace std;
bool isVisted[201][201];
int dx[] = {0, 0, 1, 1, 2, 2};
int dy[] = {1, 2, 0, 2, 0, 1};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int bucket[3];
    queue<pair<int, int>> bfs;
    set<int> ans;
    for (int i = 0; i < 3; ++i)
    {
        int _b;
        cin >> _b;
        bucket[i] = _b;
    }
    bfs.push({0, 0});
    isVisted[0][0] = true;
    ans.insert(bucket[2]);
    while (!bfs.empty())
    {
        int n1 = bfs.front().first;
        int n2 = bfs.front().second;
        int n3 = bucket[2] - n1 - n2;
        bfs.pop();
        for (int i = 0; i < 6; ++i)
        {
            int arr[] = {n1, n2, n3};
            arr[dx[i]] += arr[dy[i]];
            arr[dy[i]] = 0;
            if (arr[dx[i]] > bucket[dx[i]])
            {
                arr[dy[i]] = arr[dx[i]] - bucket[dx[i]];
                arr[dx[i]] = bucket[dx[i]];
            }
            if (!isVisted[arr[0]][arr[1]])
            {
                isVisted[arr[0]][arr[1]] = true;
                bfs.push({arr[0], arr[1]});
                if (!arr[0])
                {
                    ans.insert(arr[2]);
                }
            }
        }
    }
    for (int a : ans)
    {
        cout << a << " ";
    }
    return 0;
}

풀이

2지점만 확인해주면 나머지 지점은 정해져있기에 2지점에 대해서 진행하면 된다.
다른 곳으로 물을 옮기는 것을 반복문으로 해결하는 방법이 생각안나서 하드코딩하는 방법으로 해결해야 하나 싶었다. (A->B, A->C, B->A ... )
다른 블로그에서 확인해서 해결했다.

시작하는 곳과 도착하는 곳에 대한 배열을 작성하고 돌리면 되는 것이다. 비슷한 방법을 알고 있기도 했고 배열을 써야 한다는 것까지 생각은 했는데 도달은 못 했던 것 같다.
탐색 문제를 많이 풀어봐야겠다.