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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 N이 최대 10이기 때문에 모든 경우를 생각해보면 3종류의 원판을 순서대로 하노이 탑의 막대에 놓는 것과 같다. 그러므로 최대 (3^10)의 경우의 수만 고려하면 된다. (물론 중복 경우도 있기 때문에 실제로는 더 적을 것이다.)

 

잘 생각해보면 하노이탑을 정상적으로 만드는데 걸리는 최소 횟수를 구하는 것이므로, 각 막대에서 다른 막대로 원판을 옮기는 경우를 BFS로 구하면 빠르게 계산할 수 있다.

 

왜냐하면 BFS로 구할 경우 처음 하노이 탑이 정상적으로 완성 되는 경우가 가장 적게 원판을 이동시켜 정상적으로 만든 경우가 되기 때문이다.

 

여기서 중복되는 경우를 체크하기 위해 Set을 이용했다.

 

그러면 하노이탑이 완성되었는지 체크하는 함수와, BFS만 구현하면 문제를 해결 할 수 있다.

 

 

[아이디어 정리]

1. N이 작아 모든 경우의 수가 (3^10)이하이므로 BFS로 탐색할 수 있다.
2. 이때, 하노이 탑을 정상적으로 만드는 가장 적은 횟수를 구하는 문제이기 때문에 BFS를 이용해 가장 먼저 하노이 탑이 정상적으로 되는 경우를 빠르게 찾을 수 있다.
3. 탐색 중 이전에 만들어진 하노이 탑의 모습은 중복이므로 이를 제거하기 위해 Set을 이용한다.

 

Code

 

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include <set>
using namespace std;

char ch[3] = { 'A','B','C' };

bool check(vector<string> &vv)
{
    for (int i = 0; i < 3; i++) {
        for (int j=0; j<vv[i].size(); j++)
        {
            if (vv[i][j]!=ch[i])
            {
                return false;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int h1, h2, h3;
    string str1="", str2="", str3="", ts;
    cin >> h1;
    if (h1 > 0)
        cin >> str1;
    cin >> h2;
    if (h2 > 0)
        cin >> str2;
    cin >> h3;
    if (h3>0)
        cin >> str3;
    set<vector<string>> s;
    vector<string> v(3),tmp(3);
    v[0] = str1, v[1] = str2, v[2] = str3;
    s.insert(v);
    queue<pair<vector<string>, int>> q;
    pair<vector<string>, int> p, tp;
    q.push({ v,0 });
    int answer = 1987654321;
    while(!q.empty())
    {
        tp = q.front();
        v = tp.first;
        q.pop();
        if (check(tp.first))
        {
            answer = min(answer, tp.second);
            break;
        }
        if (tp.second>answer)
        {
            break;
        }
        for (int i=0; i<3; i++)
        {
            for (int j=0; j<3; j++)
            {
                if (i!=j)
                {
                    tmp = v;
                    if (v[i].size()>0)
                    {
                        tmp[i] = v[i].substr(0, v[i].size() - 1);
                        tmp[j] += v[i][v[i].size() - 1];
                    }
                    if (s.find(tmp) == s.end())
                    {
                        q.push({tmp, tp.second + 1});
                        s.insert(tmp);
                    }
                }
            }
        }
    }
    cout << answer << endl;

    return 0;
}

---

 

 

오랜만에 문제를 풀었더니 너무 안풀렸다;;

 

그리고 생각보다 풀이가 잘 생각나지 않는 문제였다

개선을 하려면 string이 복사가 되는 부분과 set으로 체크하는 부분을 다른 자료구조나 struct를 이용해 해결할 수 있을 것 같다

 

그리고 당분간은 코드포스에 집중할듯...

 

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