(C++) BOJ 백준 1525 퍼즐 / BFS, unordered_map

---

문제 설명

 

입력에서 무작위로 섞어져있는 3x3 퍼즐을 입력으로 준다. 이 퍼즐을 문제 맨 위에 있는 그림과 같이 초기 상태로 만드는데에 걸리는 최소 횟수를 구하는 문제다.

---

문제 풀이

 

기본적인 BFS 문제와 같이 visit 처리를 해주면서 초기상태와 같아졌을때에 depth 혹은 count를 출력하면 된다.
하지만 보드가 2차원 배열에 해당하기 때문에 이를 unordered_map의 키값으로 visit 처리를 해주기 위해서 2차원 배열의 숫자를 문자열로 바꿔주는 함수를 추가해서 visit 처리와 bfs의 값으로 이용하는 과정에서 사용했다.

---

코드

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
#define FOR(i,N) for(int i=1; i<=N; i++)
int board[4][4];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
unordered_map<string,int> board_map;
void printBoard(int board[][4]) {
    FOR(i,3) {
        FOR(j,3) cout << board[i][j] << " ";
        cout << endl;
    }
}
string boardToString(int board[][4]) {
    string str = "";
    FOR(i,3)FOR(j,3) str += to_string(board[i][j]);
    return str;
}
int bfs() {
    queue<pair<string,int>> q;
    q.push({boardToString(board),0});
    board_map[boardToString(board)] = 1;
    while(!q.empty()) {
        string cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(cur == "123456780") return cnt;
        int tempBoard[4][4];
        FOR(i,3)FOR(j,3) tempBoard[i][j] = cur[(i-1)*3+j-1]-'0';
        FOR(i,3)FOR(j,3) {
            if(tempBoard[i][j] == 0) {
                for(int k=0; k<4; k++){
                    int X = i + dx[k];
                    int Y = j + dy[k];
                    if(X<1||Y<1||X>3||Y>3) continue;
                    else {
                        // cout << "before swap" << endl;
                        // printBoard(tempBoard);
                        swap(tempBoard[i][j], tempBoard[X][Y]);
                        string next = boardToString(tempBoard);
                        if(board_map.find(next)==board_map.end()) {
                            board_map[next] = 1;
                            q.push({next,cnt+1});
                        }
                        // cout << "after swap" << endl;
                        // printBoard(tempBoard);
                        swap(tempBoard[i][j], tempBoard[X][Y]);
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    FOR(i,3)FOR(j,3) cin >> board[i][j];
    cout << bfs();
    return 0;
}