백준 1525번. 퍼즐(c++) / BFS

BFS 자체는 어렵지 않았지만, 퍼즐의 상태를 어떻게 저장할지가 굉장히 까다롭게 느껴졌다.

2차원 배열에 저장하려고 했지만,,, 어떻게 보면 BruteForce로 모든 경우를 다 돌아야하기 때문에

2차원으로 한다면,,,, 아주 복잡해지고 메모리도 많이 차지할 것으로 생각되었다.

따라서, 다른 고수분들을 어떻게 코드를 짜셨을까 보다가 대부분 String형태로 저장해놓고 0의 인덱스 값을 찾아서

그것을 2차원 배열의 (x, y) 값으로 바꾸고 인접한 곳과 자리를 바꾸는 형식으로.,,,,

구현하셨더라,,, 아주 최적화된 좋은 방법이라 생각되어 그렇게 구현해보았다.

 

즉, 2차원 배열의 형태로 되어있어야 bfs를 하기 쉽기 때문에

퍼즐의 상태를 한눈에 보기 쉽게 해서 0의 위치를 찾을 때에는 => String형태

BFS를 돌기 위해서는(0주위에 있는 좌표와 swap을 하기 위해) => 2차원 배열의 형태

이렇게 나눠주었고

 

String -> 2차원 배열의 좌표

2차원 배열의 좌표 -> String

이렇게 변환해주는 것은 간단한 연산을 통해 해결했다. (코드 참조)

 

// 퍼즐
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <string>
 
using namespace std;
 
int puzzle[4][4] = { 0, };
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
 
string arrayToString()
{
    string tmp = "";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            tmp += (puzzle[i][j]+'0');
        }
    }
    return tmp;
}
 
int move()
{
    queue<pair<string, int>> q;
    map<string, int> check;
 
    q.push(make_pair(arrayToString(), 0));
    while (!q.empty()) {
        string s = q.front().first;
        int cnt = q.front().second;
        check[s] = 1;
        q.pop();
 
        if (s == "123456780") {
            return cnt;
        }
 
        int idx = s.find('0');
        int x = idx / 3;
        int y = idx % 3;
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < 3 && 0 <= ny && ny < 3) {
                string tmp = s;
                swap(tmp[x * 3 + y], tmp[nx * 3 + ny]);
 
                if (check.count(tmp) == 0) {
                    check[tmp] = 1;
                    q.push(make_pair(tmp, cnt + 1));
                }
            }
        }
    }
    return -1;
}
 
int main()
{
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> puzzle[i][j];
        }
    }
 
    cout << move() << "\n";
 
    return 0;
}