[ 백준 12906 ] 새로운 하노이 탑 (C++)

백준의 새로운 하노이탑(12906) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 하노이 타워 게임을 하는데, 원래의 방식과 달리 1번막대에는 A번 원판만, 2번막대에는 B번원판만, 3번막대에는 C번

   원판만 존재하게끔 만드는데 총 몇번을 움직여야 되는지 구해야 하는 문제이다.

   본인은 현재 상태에서, BFS를 이용해서 완전탐색하는 방식으로 구현해 보았다.

   원판의 상태들을 문자열을 이용해서 관리해주었다. 먼저 입력받을 때도, 원판이 존재하는 막대들이 존재했다. 따라서

   각 막대에 들어있는 원판의 갯수를 입력받는데, 그 갯수가 0개라면 문자열 "" 을 저장시켜주고 탐색을 진행하였다.

2) 1)에서도 말했듯이, 본인은 각 막대들에 꽂혀있는 원판을 문자열을 이용해서 관리해주었다.

   BFS에서는 모든 경우를 다 해 주었다.

   여기서 모든 경우라는 것은

   1. 막대 1번에 1개이상의 원판이 있을 때, 2번막대로 주는경우 3번막대로 주는경우

   2. 막대 2번에 1개이상의 원판이 있을 때, 1번막대로 주는경우 3번막대로 주는경우

   3. 막대 3번에 1개이상의 원판이 있을 때, 1번막대로 주는경우 2번막대로 주는경우

   그렇다면 문자열로 관리하면서 막대에 원판이 1개 이상 있다는 것을 어떻게 어떻게 판단할까?

   바로 문자열의 길이로 판단할 수 있다. 문자열의 길이가 0보다 크다라는 것은, 문자가 최소 1개는 존재하는 문자열이라는 것이고

   이는 막대에 원판이 최소 1개 이상 있다는 의미이기 때문이다.

  

   또 하나의 문제는 중복처리였다. 문자열이기 때문에 일반적인 배열로는 관리할 수 없었기에 STL set을 이용해서 중복체크를

   해 주었다. 아직 한번도 존재하지 않았던 원판의 분포라면, 탐색을 계속해서 진행하지만, 이미 기존에 한번이라도 존재했었던

   원판의 분포라면 중복적으로 탐색을 해주지 않았다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<set>
 
#define endl "\n"
using namespace std;
 
set<pair<pair<string, string>, string>> Visit;
 
typedef struct
{
    string S1;
    string S2;
    string S3;
}State;
 
State Hanoi;
string A, B, C;
 
void Input()
{
    int Idx = 0;
    for (int i = 0; i < 3; i++)
    {
        int a; cin >> a;
        if (Idx == 0)
        {
            if (a == 0)
            {
                A = "";
                Hanoi.S1 = A;
                Idx++;
            }
            else
            {
                cin >> A;
                Hanoi.S1 = A;
                Idx++;
            }            
        }
        else if (Idx == 1)
        {
            if (a == 0)
            {
                B = "";
                Hanoi.S2 = B;
                Idx++;
 
            }
            else
            {
                cin >> B;
                Hanoi.S2 = B;
                Idx++;
            }
        }
        else 
        {
            if (a == 0)
            {
                C = "";
                Hanoi.S3 = C;
            }
            else
            {
                cin >> C;
                Hanoi.S3 = C;
            }
        }
    }
}
 
bool Check_Hanoi_Tower(string A, string B, string C)
{
    char Plate_A = 'A';
    char Plate_B = 'B';
    char Plate_C = 'C';
    
    if (A.length() > 0)
    {
        for (int i = 0; i < A.length(); i++)
        {
            if (A[i] != Plate_A) return false;
        }
    }
 
    if (B.length() > 0)
    {
        for (int i = 0; i < B.length(); i++)
        {
            if (B[i] != Plate_B) return false;
        }
    }
 
    if (C.length() > 0)
    {
        for (int i = 0; i < C.length(); i++)
        {
            if (C[i] != Plate_C) return false;
        }
    }
 
    return true;
}
 
string Remove_Top(string S)
{
    string Temp = "";
    for (int i = 0; i < S.length() - 1; i++)
    {
        Temp = Temp + S[i];
    }
    return Temp;
}
 
void BFS(State S, int Init)
{
    queue<pair<State, int>> Q;
    Q.push(make_pair(S, Init));
    Visit.insert(make_pair(make_pair(S.S1, S.S2), S.S3));
 
    while (Q.empty() == 0)
    {
        string Hanoi_A = Q.front().first.S1;
        string Hanoi_B = Q.front().first.S2;
        string Hanoi_C = Q.front().first.S3;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Check_Hanoi_Tower(Hanoi_A, Hanoi_B, Hanoi_C) == true)
        {
            cout << Cnt << endl;
            return;
        }
 
        if (Hanoi_A.length() > 0)
        {
            // B한테 하나주는거
            string A_Temp = Remove_Top(Hanoi_A);
            string B_Temp = Hanoi_B + Hanoi_A[Hanoi_A.length() - 1];
            if (Visit.find(make_pair(make_pair(A_Temp, B_Temp), Hanoi_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(A_Temp, B_Temp), Hanoi_C));
                State S_Temp;
                S_Temp.S1 = A_Temp; S_Temp.S2 = B_Temp; S_Temp.S3 = Hanoi_C;
                Q.push(make_pair(S_Temp, Cnt + 1));
            }
 
            string C_Temp = Hanoi_C + Hanoi_A[Hanoi_A.length() - 1];
            if (Visit.find(make_pair(make_pair(A_Temp, Hanoi_B), C_Temp)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(A_Temp, Hanoi_B), C_Temp));
                State S_Temp;
                S_Temp.S1 = A_Temp; S_Temp.S2 = Hanoi_B; S_Temp.S3 = C_Temp;
                Q.push(make_pair(S_Temp, Cnt + 1));
            }
        }
 
        if (Hanoi_B.length() > 0)
        {
            string B_Temp = Remove_Top(Hanoi_B);
            string A_Temp = Hanoi_A + Hanoi_B[Hanoi_B.length() - 1];
            if (Visit.find(make_pair(make_pair(A_Temp, B_Temp), Hanoi_C)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(A_Temp, B_Temp), Hanoi_C));
                State S_Temp;
                S_Temp.S1 = A_Temp; S_Temp.S2 = B_Temp; S_Temp.S3 = Hanoi_C;
                Q.push(make_pair(S_Temp, Cnt + 1));
            }
 
            string C_Temp = Hanoi_C + Hanoi_B[Hanoi_B.length() - 1];
            if (Visit.find(make_pair(make_pair(Hanoi_A, B_Temp), C_Temp)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Hanoi_A, B_Temp), C_Temp));
                State S_Temp;
                S_Temp.S1 = Hanoi_A; S_Temp.S2 = B_Temp; S_Temp.S3 = C_Temp;
                Q.push(make_pair(S_Temp, Cnt + 1));
            }
        }
 
        if (Hanoi_C.length() > 0)
        {
            string C_Temp = Remove_Top(Hanoi_C);
            string A_Temp = Hanoi_A + Hanoi_C[Hanoi_C.length() - 1];
            if (Visit.find(make_pair(make_pair(A_Temp, Hanoi_B), C_Temp)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(A_Temp, Hanoi_B), C_Temp));
                State S_Temp;
                S_Temp.S1 = A_Temp; S_Temp.S2 = Hanoi_B; S_Temp.S3 = C_Temp;
                Q.push(make_pair(S_Temp, Cnt + 1));
            }
 
            string B_Temp = Hanoi_B + Hanoi_C[Hanoi_C.length() - 1];
            if (Visit.find(make_pair(make_pair(Hanoi_A, B_Temp), C_Temp)) == Visit.end())
            {
                Visit.insert(make_pair(make_pair(Hanoi_A, B_Temp), C_Temp));
                State S_Temp;
                S_Temp.S1 = Hanoi_A; S_Temp.S2 = B_Temp; S_Temp.S3 = C_Temp;
                Q.push(make_pair(S_Temp, Cnt + 1));
            }
        }
    }
}
 
void Solution()
{
    BFS(Hanoi, 0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}