[알고리즘 문제] 백준1525 - 퍼즐

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

1525번: 퍼즐

 

먼저 퍼즐을 움직인 최소 횟수를 구하는 문제이기 때문에 bfs를 사용했습니다. 그리고 현재 퍼즐의 상태를 관리를 어떻게 할까 생각을 했는데, 그냥 2차원 자료구조로 저장하여 que에 넣어 bfs를 하면 메모리 초과가 날 것 같았습니다. 메모리 제한이 32 MB 이더라구요.

 

그래서 퍼즐을 문자열로 관리하였습니다 3x3이기 때문에 길이가 9인 문자열이 됩니다.

 

그리고 문자열에서 '0'의 index값을 찾아서 좌우상하(-1,1,-3,3)위치로 움직일 수 있으면 해당 문자열에서 swap을 하였습니다. 그리고 문자열의 중복을 피하기 위해 set을 사용하였습니다.

 

주의할 점은 '0' 퍼즐을 상/하/좌/우로 움직일 때 처음에 범위가 0~8사이인지만 검사를 하였는데 생각해보니 원래 3x3 크기의 퍼즐이고 x축에서 첫번째/마지막 위치에서는 왼쪽/오른쪽으로 움직일 수 없기 때문에 이부분을 따로 처리해 주었습니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

bool check(string s, vector<string> vec)
{
    return find(vec.begin(), vec.end(), s) == vec.end() ? false : true;
}
int main()
{
    string input = "";
    for (int i = 0; i < 9; i++)
    {
        int n;
        cin >> n;
        input += to_string(n);
    }

    int dir[4] = {-1, 1, -3, 3};

    queue<string> que;
    set<string> visited;

    int count = 0;
    int index;

    string str;
    char temp;

    visited.insert(input);
    que.push(input);

    while (!que.empty())
    {
        int size = que.size();

        for (int i = 0; i < size; i++)
        {

            str = que.front();
            que.pop();

            if (str == "123456780")
            {
                cout << count;
                return 0;
            }

            index = str.find("0");
            string s;

            for (int i = 0; i < 4; i++)
            {
                int swapIndex = index + dir[i];
                if (swapIndex < 0 || swapIndex >= 9 || (index % 3 == 0 && i == 0) || (index % 3 == 2) && i == 1)
                {
                    continue;
                }
                s = str;
                swap(s[index], s[swapIndex]);
                if (visited.count(s) == 0)
                {
                    visited.insert(s);
                    que.push(s);
                }
            }
        }
        count++;
    }

    cout << -1;
    return 0;
}