[BOJ 12906] 새로운 하노이 탑

#문제

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

#풀이

은근 시간이 많이 걸렸던 문제입니다.

딱 문제를 보자마자 모든 경우의 수를 해봐야겠다! 라는 생각이 들었습니다.

저는 모든 경우의 수를 돌릴 때에는 대부분 DFS로 했기 때문에 해당 문제도 그렇게 접근하려 했습니다.

하지만, 원판을 내 마음대로 뽑을 수 있는 것이 아니라 무조건 맨 위에있는 원판 만 움직일 수 있으므로 풀이가 쉽지 않았습니다.

결국... 구글링... :)

풀이가 많이 있지도 않았습니다... 아직 많이 풀어보지 않은 문제라 그런가 봅니다...

딱 한가지 풀이가 있었는데 BFS를 이용하였습니다.(참고 사이트)

BFS로 모든 경우의 수를 돌리는 것이 이해가 더 잘 오기에 BFS로 풀게 되었습니다.

큐에 넣을 때는 현재 탑들의 상황과 해당 상황이 오기까지 원판을 몇번 옮겼는가를 저장해 둡니다.

큐에 넣었을 때 중복되는 상황들을 막기 위해 Set을 사용하여 중복을 막아 줍니다.

이 후 큐에서 뺄 때마다 해당 상황이 끝인가를 판단해주고, 만약 끝이라면 같이 저장한 움직임의 횟수를 출력합니다.

이와 비슷한 문제들이 있습니다.

같이 풀어보시면 좋을듯 합니다!

[돌 그룹] : https://www.acmicpc.net/problem/12886

[4 연산] :  https://www.acmicpc.net/problem/14395

#코드

#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;
 
struct Hanoi{
    string sticks[3];
    int cnt;
};
 
bool operator<(const Hanoi& h1, const Hanoi& h2){
    if(h1.sticks[0] == h2.sticks[0]){
        if(h1.sticks[1] == h2.sticks[1]){
            return h1.sticks[2] < h2.sticks[2];
        }
        return h1.sticks[1] < h2.sticks[1];
    }
    return h1.sticks[0] < h2.sticks[0];
}
 
Hanoi hanoi;
set<Hanoi> visit;
 
bool checkingFinish(string A, string B, string C){
    for(int i = 0; i < A.size(); i++){
        if(A[i] != 'A') return false;
    }
    for(int i = 0; i < B.size(); i++){
        if(B[i] != 'B') return false;
    }
    for(int i = 0; i < C.size(); i++){
        if(C[i] != 'C') return false;
    }
    return true;
}
 
void playTheHanoi(){
    queue<Hanoi> q;
    q.push(hanoi);
    visit.insert(hanoi);
    while(!q.empty()){
        string stickA = q.front().sticks[0];
        string stickB = q.front().sticks[1];
        string stickC = q.front().sticks[2];
        int cnt = q.front().cnt;
        q.pop();
    
        //들어온 값을 확인하여 끝났는지 확인
        if(checkingFinish(stickA, stickB, stickC)){
            cout << cnt << endl;
            return;
        }
        
        //A에서 다른 막대기로
        if(!stickA.empty()){
            //맨 위, 즉 맨 마지막 문자를 빼서 옮긴다.
            string nextStickA = stickA.substr(0,stickA.size()-1);
            char movingPlate = stickA[stickA.size()-1];
            
            Hanoi h;
            h.cnt = cnt + 1;
            // A -> B
            h.sticks[0] = nextStickA;
            h.sticks[1] = stickB + movingPlate;
            h.sticks[2] = stickC;
            if(visit.find(h) == visit.end()){
                q.push(h);
                visit.insert(h);
            }
            // A -> C
            h.sticks[0] = nextStickA;
            h.sticks[1] = stickB;
            h.sticks[2] = stickC + movingPlate;
            if(visit.find(h) == visit.end()){
                q.push(h);
                visit.insert(h);
            }
        }
        //B에서 다른 막대기로
        if(!stickB.empty()){
            //맨 위, 즉 맨 마지막 문자를 빼서 옮긴다.
            string nextStickB = stickB.substr(0,stickB.size()-1);
            char movingPlate = stickB[stickB.size()-1];
            
            Hanoi h;
            h.cnt = cnt + 1;
            // B -> A
            h.sticks[0] = stickA + movingPlate;
            h.sticks[1] = nextStickB;
            h.sticks[2] = stickC;
            if(visit.find(h) == visit.end()){
                q.push(h);
                visit.insert(h);
            }
            // B -> C
            h.sticks[0] = stickA;
            h.sticks[1] = nextStickB;
            h.sticks[2] = stickC + movingPlate;
            if(visit.find(h) == visit.end()){
                q.push(h);
                visit.insert(h);
            }
        }
        //C에서 다른 막대기로
        if(!stickC.empty()){
            //맨 위, 즉 맨 마지막 문자를 빼서 옮긴다.
            string nextStickC = stickC.substr(0,stickC.size()-1);
            char movingPlate = stickC[stickC.size()-1];
            
            Hanoi h;
            h.cnt = cnt + 1;
            // C -> A
            h.sticks[0] = stickA + movingPlate;
            h.sticks[1] = stickB;
            h.sticks[2] = nextStickC;
            if(visit.find(h) == visit.end()){
                q.push(h);
                visit.insert(h);
            }
            // C -> B
            h.sticks[0] = stickA;
            h.sticks[1] = stickB + movingPlate;
            h.sticks[2] = nextStickC;
            if(visit.find(h) == visit.end()){
                q.push(h);
                visit.insert(h);
            }
        }
    }
}
 
int main(){
    for(int i = 0; i < 3; i++){
        int num;
        cin >> num;
        if(num != 0)
            cin >> hanoi.sticks[i];
    }
    hanoi.cnt = 0;
    playTheHanoi();
    return 0;
}