[백준/C++] #1525 퍼즐 (BFS)

문제

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

 

구상

빈칸을 움직여서 배열의 상태가 원하는 상태로 나오게끔 하는데, 이때의 최소 이동 횟수를 구하는 문제였다. 최소 이동 횟수를 구하는 것이다 보니 bfs를 이용하는 문제라는 건 인지했지만, 원하는 상태로 바꾸는 데에 있어서 빈칸을 언제까지 움직여볼 것인가에 대한 고민이 들었다. 단순하게 방문했는지의 여부를 판단하기에는 빈칸을 움직이는 순서에 따라서 상황이 다양하게 바뀔 수 있었다. 그래서 그 이전에 해당 상황에 도달한 적이 없다면, 큐에 넣는 방식을 택했다. 
*map의 find(key) 결과값이 map.end()값과 같다면, 원소가 없다는 뜻이다.
*만일 원소가 있다면, map<Key, T>::iterator 를 반환하고, iterator는 -> 연산자를 사용하여 std::pair<const Key, T> 타입의 값을 참조할 수 있다. ex) auto it = myMap.find(key); string key = it -> first; int value = it -> second
 
처음에는 3*3 2중 벡터를 사용했었는데, 이동횟수를 배열 상태와 map으로 매핑하기가 불편해서 배열 크기도 정해져있겠다 3*3 배열로 되어있는 퍼즐의 상태를 string으로 변환해서 사용했다. 빈칸을 움직일 때에는 string에서의 빈칸 인덱스를 사용하여 배열 상에서의 빈칸의 위치(x, y좌표)를 알아낸 다음 어디로 이동할 수 있는지 판단하고, 이동할 수 있는 곳의 배열상 위치를 string 상의 인덱스로 변환하여 swapping 해주었다. 
 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
// 1525 퍼즐

string answer = "123456780";
string now = "";
map<string, int> mov; // 상태와 해당 상태에 도달하기 위한 횟수
queue<string> q;
vector<pair<int, int>> dxy = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
int res = -1;

void solution() { // bfs
    while (!q.empty()) {
        string curr = q.front();
        q.pop();

        if (curr == answer) {
            res = mov[curr];
            return;
        }

        // 0 위치 찾기
        int idx = curr.find('0');
        int x = idx % 3;
        int y = idx / 3;

        for (int i = 0; i < 4; i++) {
            int n_x = x + dxy[i].first;
            int n_y = y + dxy[i].second;
            int n_idx = n_y * 3 + n_x;

            if (n_x < 0 || n_x >= 3 || n_y < 0 || n_y >= 3) continue; // 경계에서 벗어났을 때

            string next = curr;
            swap(next[idx], next[n_idx]); // 원소 두개 바꾸기
            if (mov.find(next) == mov.end()) { // 방문 여부를 확인하는게 아니라, 이전에 나왔던 상태인지의 여부를 판단하는 것. 
                q.push(next);
                mov[next] = mov[curr] + 1;
            }
        }
    }
   
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            string a; cin >> a; 
            now.append(a);
        }
    }
    q.push(now); 
    mov[now] = 0;

    // 로직
    solution();

    // 출력
    cout << res;

    return 0;

}