물통 옮기기

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

2251번: 물통

 

세 물통에 담긴 물의 양을 하나의 상태(정점)로본다.

물을 옮기는 행위를 하고나서

다시 상태를 확인한다.

 

문제를 풀며 어려웠던 점은

a->b, b->a

과 같이 물통을 옮기는 과정을 직접 구현했었어야 했다.

그 이유는 물통의 다음 상태를 알 수 없었기 때문이다.

겪어봤던 탐색 문제는 다음 정점을 알 수 있었지만

알 수 없는 경우에는 현재 정점에서 가능한 "행위"를 시행하여 다음 정점을 만들어야 한다.

 

#include <iostream>
#include <set>

using namespace std;

std::set<int> res;

struct state{
    int bottle[3];                      // 현재의 세 물병의 물 양을 나타냄
};
int bmax[3];                                // 각 물병의 최대치를 나타냄
int from[] = { 0, 0, 1, 1, 2, 2 };          // 물을 주는 통
int to[] =   { 1, 2, 0, 2, 0, 1 };          // 물을 받는 통
bool visit[205][205][205] = {0, };                   // 두 보틀의 숫자를 visit으로 함 왜냐면 두개만 알아도 나머지 하나의 숫자를 알 수 있기때문

void dfs(int a, int b, int c){
    // std::cout << next.bottle[0] << next.bottle[1] << next.bottle[2] << '\n';
    if(a == 0){
        res.insert(c);
    }

    visit[a][b][c] = true;

    for(int i = 0; i < 6; i++) {                    // 두 물병을 선택함
        state next;
        next.bottle[0] = a; next.bottle[1] = b; next.bottle[2] = c;
        //std::cout << next.bottle[0] << next.bottle[1] << next.bottle[2] << "a\n";


        if(next.bottle[to[i]] + next.bottle[from[i]] <= bmax[to[i]]){         // 물 붓는 과정인데 확인 해야함 누가 더 큰지 얼만큼 넣어야 하는지
            next.bottle[to[i]] += next.bottle[from[i]];
            next.bottle[from[i]] = 0;
        } else{ 
            next.bottle[from[i]] -= bmax[to[i]] - next.bottle[to[i]];
            next.bottle[to[i]] = bmax[to[i]];
        }

        if(!visit[next.bottle[0]][next.bottle[1]][next.bottle[2]]){
            //std::cout << next.bottle[0] << next.bottle[1] << next.bottle[2] << "b\n";
            dfs(next.bottle[0], next.bottle[1], next.bottle[2]);
        }
    }
}

int main(){
    std::cin >> bmax[0] >> bmax[1] >> bmax[2];
    dfs(0, 0, bmax[2]);
    std::set<int>::iterator it;
    for(it = res.begin(); it != res.end(); it++){
        std::cout << *it << " ";
    }
}