퍼즐

백준 1525번: 퍼즐

아이디어

좀 어려운 BFS문제다. 우선 퍼즐을 표현할 때 문자열으로 표현했다. 2차원 배열로 표현하면 map의 key로 사용할 수 없기 때문이다.(근데 이거 포인터로 하면 될것같기도?… 잘 모르겠다.) 또 일반적으로는 visited 배열로 방문했음을 표시하지만 이번에는 map에 표시했다. key는 퍼즐 상태, value는 이동 횟수로 저장했다. 9!이라 1차원 배열 만들어서 표시해도 됐을거같은데 이렇게 풀면 4*4 퍼즐도 풀 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

map<string, int> m;
queue<string> q;

vector<string> get_boards(string str) {
    vector<string> ret;
    int zero = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '0') zero = i;
    }
    if (zero-3 >= 0) {
        string s = str;
        string c;
        c += str[zero-3];
        s.replace(zero-3, 1, "0");
        s.replace(zero, 1, c);
        ret.push_back(s);
    }
    if (zero%3 != 2) {
        string s = str;
        string c;
        c += str[zero+1];
        s.replace(zero+1, 1, "0");
        s.replace(zero, 1, c);
        ret.push_back(s);
    }
    if (zero%3 != 0) {
        string s = str;
        string c;
        c += str[zero-1];
        s.replace(zero-1, 1, "0");
        s.replace(zero, 1, c);
        ret.push_back(s);
    }
    if (zero+3 < 9) {
        string s = str;
        string c;
        c += str[zero+3];
        s.replace(zero+3, 1, "0");
        s.replace(zero, 1, c);
        ret.push_back(s);
    }
    return ret;
}

void bfs() {
    while (!q.empty() && m["123456780"] == 0) {
        string s = q.front();
        q.pop();
        vector<string> boards = get_boards(s);
        for (auto x : boards) {
            if (!m[x] || m[x] > m[s] + 1) {
                m[x] = m[s] + 1;
                q.push(x);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    char ch;
    string input;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> ch;
            input += ch;
        }
    }
    m[input] = 1;
    q.push(input);
    bfs();
    if (input == "123456780") cout << 0;
    else cout << m["123456780"] - 1;
    return 0;
}

여담

C++ 문자열 다루기 너무 힘들다. 파이썬 마렵다. 내가 더럽게 짠건가?