[BaekJoon/백준] 2251번 물통

 

나는 DFS로 풀었는데,

 

BFS로 정말 깔끔하게 푸신 분이 있어서.. 추가적으로 본문 맨 아래에 게시해야겠다.

 

 

핵심은, 무한 반복을 방지하기 위해

SnapShot 배열(A, B, C 물이 특정하게 채워져 있는 경우의 리스트)을 만들어 놓는 것이다.

 

그리고 이미 접근한 경우라면, dfs를 진행하지 않는 것이다.

// key point : A . B . C 스냅샷이 똑같으면 그만둠.

#include <iostream>
#include <set>

using namespace std;

bool SnapShot[201][201][201];

int B_SIZE[3]; // 0 1 2 = A B C. 보틀 사이즈
int Bottle[3]; // 0 1 2 = A B C. 물이 들어있는 양

set<int> s;

void dfs(int index) { // 물을 주는 주체 = index
    
    if(Bottle[0] == 0)
        s.insert(Bottle[2]);
    
    SnapShot[Bottle[0]][Bottle[1]][Bottle[2]] = true;
    
    
    // + 1, + 2를 사용하기 위해 1 ~ 2 까지.
    for(int i = 1; i < 3; i++) {
        
        int candidate = (index + i) % 3;
        
        if(Bottle[candidate] < B_SIZE[candidate]) { // 채울 후보가 아직 꽉 차지 않았다면.
            
            int gap = B_SIZE[candidate] - Bottle[candidate]; // 채울 수 있는 물의 양

            int b1 = Bottle[candidate]; // 백업
            int b2 = Bottle[index]; //  백업

            if(Bottle[index] >= gap) { // 채우고도 남거나, 딱 맞을 경우
                
                Bottle[candidate] = B_SIZE[candidate];
                Bottle[index] -= gap;
                                
            } else { // 채우기엔 부족한 경우
                
                Bottle[candidate] += Bottle[index];
                Bottle[index] = 0;
                        
            }
            
            
            if(!SnapShot[Bottle[0]][Bottle[1]][Bottle[2]]) { // 스냅샷이 없을 경우에만 dfs 진행. 아니면 그냥 원상복구.
                // 어디서부터 다시 시작할지가 중요. dfs(candidate)를 하게 되면, 준 곳에서만 시작이 되므로. 이렇게 for문으로.
                // 비어 있지 않은 어느 곳에서든 시작 가능.
                for(int i = 0; i < 3; i++) {
                    if(Bottle[i] != 0) {
                        dfs(i);
                    }
                }
            }

            Bottle[candidate] = b1;
            Bottle[index] = b2;
            
        }
    }
}


int main() {
    
    cin >> B_SIZE[0] >> B_SIZE[1] >> B_SIZE[2];

    Bottle[2] = B_SIZE[2]; // 세번째 보틀에는 처음에 물이 꽉 차 있음.
    
    dfs(2); // 세번째 보틀부터 시작.
    
    
    for(auto i = s.begin(); i != s.end(); i++) {
        cout << (*i) << " ";
    }
}

 

 

 

https://lu-coding.tistory.com/6

[백준] 2251번 : 물통 (C++)