1525번: 퍼즐

퍼즐을 풀어서 1차원 형태의 문자열을 사용해 문제를 해결했다.

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
 
typedef struct {
    int y, x;
} dif;
 
dif dir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
 
int move(int row, int col) {
    return (3 * row) + col;
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    std::string str;
    long long sum = 0;
    int tmp = 0;
    for (int i = 0; i < 9; i++) {
        std::cin >> tmp;
        if (tmp == 0) tmp = 9;
        sum += tmp;
        sum *= 10;
    }
    sum /= 10;
 
    str = std::to_string(sum);
 
    std::queue<std::pair<std::string, int>> mQ;
    std::map<std::string, int> mM;
    mQ.push({ str, 0 });
    mM.insert(std::make_pair(str, 5));
    while (!mQ.empty()) {
        std::string val = mQ.front().first;
        int count = mQ.front().second;
        mQ.pop();
        
        if (val == "123456789") {
            std::cout << count << "\n";
            str = val;
            break;
        }
 
        int cur = 0;
        for (int i = 0; i < 9; i++) {
            if (val[i] == '9') {
                cur = i;
                break;
            }
        }
 
        int row = cur / 3;
        int col = cur % 3;
 
        for (int i = 0; i < 4; i++) {
            int tempY = row + dir[i].y;
            int tempX = col + dir[i].x;
            if (tempY < 0 || tempY > 2 || tempX < 0 || tempX > 2) continue;
            int pos = move(tempY, tempX);
            val[cur] = val[pos];
            val[pos] ='9';
            if (mM.find(val) == mM.end()) {
                mM.insert(std::make_pair(val, 5));
                mQ.push({ val, count + 1 });
            }
            val[pos] = val[cur];
            val[cur] = '9';
        }
    }
 
    if (str != "123456789") {
        std::cout << -1 << "\n";
    }
    return 0;
}