[BFS] 12906번 새로운 하노이 탑

12906번 새로운 하노이 탑

 

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

 

문제

오늘은 새로운 하노이 탑 게임을 해보려고 한다. 이 게임의 규칙은 다음과 같다.

• 막대는 총 세 가지 종류가 있다. 막대 A, 막대 B, 막대 C
• 게임이 시작될 때, 각각의 막대에는 0개 또는 그 이상의 원판이 놓여져 있다.
• 모든 원판의 크기는 같으며, 원판의 종류도 A, B, C로 세 가지가 있다. 원판은 원판 A, 원판 B, 원판 C와 같이 표현한다.
• 한 번 움직이는 것은 한 막대의 가장 위에 있는 원판을 다른 막대의 가장 위로 옮기는 것이다.
• 게임의 목표는 막대 A에는 원판 A만, 막대 B는 원판 B만, 막대 C는 원판 C만 놓여져 있어야 한다.
• 되도록 최소로 움직여야 한다.

막대 A, 막대 B, 막대 C에 놓여져 있는 원판의 상태가 주어졌을 때, 게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주어진다. 막대의 상태는 밑에 있는 원판부터 주어진다.

각 막대의 상태는 A, B, C로만 이루어진 문자열이며, 모든 막대에 놓여져 있는 원판 개수의 합은 1보다 크거나 같고, 10보다 작거나 같다.

 

출력

게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 출력한다.

 

예제 입력

1 A
2 AA
2 AA

1 B
1 C
1 A

3 CBA
0
0

 

예제 출력

4

5

5

 

해결방법

BFS 탐색을 통해 최단거리를 찾는 문제이다

 

문제를 접하고 머리속으로는 개념이 잡히는데 어떻게 구현해야 할지가 막막했다

스택? 벡터? 문자열?

처음에는 스택으로 해보려다가 STL 을 잘 활용할 자신이 없어서 문자열로 갈아탔다…ㅎㅎ

 

구조체를 사용하여 하노이의 상태를 큐에 저장하기로 했다

struct node {
    string strA,strB,strC;
    int cnt;
    
    node() {}
    node(string _strA,string _strB,string _strC,int _cnt)
    : strA(_strA),strB(_strB),strC(_strC),cnt(_cnt) {}
};

 

아 그리고 문자열을 처리하다가 새로운 사실을 발견했다

문자열의 마지막을 가져오고, 마지막을 지우는 작업이 필요했는데 구글링을 통해 편한 방법을 찾았다!

if(!str.empty()){
    char lastElement = str[str.size()-1];
    str.pop_back();
}

 

마지막으로 중복처리가 가장 관건이었다

하노이의 탑 상태를 문자열로 저장했기 때문에 3개의 문자열이 존재했다

이 문자열을 가운데 / 를 포함시켜 합친 뒤, set으로 중복처리를 진행했다

// A → B
string d = na + "/" + sB+move + "/" + sC;
if(visited.find(d) == visited.end()){
    q.push(node(na,sB+move,sC,cnt+1));
    visited.insert(d);
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 11
#define INF 987654321
using namespace std;

struct node {
    string strA,strB,strC;
    int cnt;
    
    node() {}
    node(string _strA,string _strB,string _strC,int _cnt)
    : strA(_strA),strB(_strB),strC(_strC),cnt(_cnt) {}
};

int a,b,c;
char ch;
string strA,strB,strC,d;

set<string> visited;

bool is_ans(string sA,string sB,string sC){
    for(int i=0 ;i<sA.size(); i++){
        if(sA[i] != 'A') return false;
    }
    
    for(int i=0 ;i<sB.size(); i++){
        if(sB[i] != 'B') return false;
    }
    
    for(int i=0 ;i<sC.size(); i++){
        if(sC[i] != 'C') return false;
    }
    return true;
}

void bfs(node n){
    queue<node> q;
    q.push(n);
    d = n.strA + "/" + n.strB + "/" + n.strC;
    visited.insert(d);
    
    while(!q.empty()){
        string sA = q.front().strA;
        string sB = q.front().strB;
        string sC = q.front().strC;
        int cnt = q.front().cnt;
        q.pop();
        
        // 정답을 찾은 경우
        if(is_ans(sA,sB,sC)){
            cout << cnt << "\n";
            return;
        }
        
        // A 막대에서 다른 막대로 이동
        if(!sA.empty()){
            string na = sA;
            na.pop_back();
            char move = sA[sA.size()-1];
            
            // A → B
            d = na + "/" + sB+move + "/" + sC;
            if(visited.find(d) == visited.end()){
                q.push(node(na,sB+move,sC,cnt+1));
                visited.insert(d);
            }
            
            // A → C
            d = na + "/" + sB + "/" + sC+move;
            if(visited.find(d) == visited.end()){
                q.push(node(na,sB,sC+move,cnt+1));
                visited.insert(d);
            }
        }
        
        // B 막대에서 다른 막대로 이동
        if(!sB.empty()){
            string nb = sB;
            nb.pop_back();
            char move = sB[sB.size()-1];
            
            // B → A
            d = sA+move + "/" + nb + "/" + sC;
            if(visited.find(d) == visited.end()){
                q.push(node(sA+move,nb,sC,cnt+1));
                visited.insert(d);
            }
            
            // B → C
            d = sA + "/" + nb + "/" + sC+move;
            if(visited.find(d) == visited.end()){
                q.push(node(sA,nb,sC+move,cnt+1));
                visited.insert(d);
            }
        }
        
        // B 막대에서 다른 막대로 이동
        if(!sC.empty()){
            string nc = sC;
            nc.pop_back();
            char move = sC[sC.size()-1];
            
            // C → A
            d = sA+move + "/" + sB + "/" + nc;
            if(visited.find(d) == visited.end()){
                q.push(node(sA+move,sB,nc,cnt+1));
                visited.insert(d);
            }
            
            // C → B
            d = sA + "/" + sB+move + "/" + nc;
            if(visited.find(d) == visited.end()){
                q.push(node(sA,sB+move,nc,cnt+1));
                visited.insert(d);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    // A 막대 입력
    strA = "";
    cin >> a;
    for(int i=0; i<a; i++){
        cin >> ch;
        strA += ch;
    }
    
    // B 막대 입력
    strB = "";
    cin >> b;
    for(int i=0; i<b; i++){
        cin >> ch;
        strB += ch;
    }
    
    // C 막대 입력
    strC = "";
    cin >> c;
    for(int i=0; i<c; i++){
        cin >> ch;
        strC += ch;
    }
    
    node n(strA,strB,strC,0);
    bfs(n);
    
    return 0;
}