[백준 1525] 퍼즐 (C++)

1525번: 퍼즐

BFS, 비트마스킹

---

3x3 크기의 퍼즐은 각 칸마다 0~8까지의 숫자가 들어간다는 것을 이용해서 

하나의 숫자당 4개의 비트를 사용.

long long 타입에서 총 36개의 비트를 사용해 3x3 퍼즐의 정보를 저장하도록 했다.

위 퍼즐에서 0의 위치는 3행 3열에 있다. 따라서 32번째 비트~35번째 비트 공간이 해당 칸을 저장하게된다.

그리고 특정 칸에 위치한 숫자를 알아내기 위한 mask로서 Checker배열을 설정했다.

 

BFS를 수행하면서 매번 0의 위치를 찾아준다.

0의 위치를 찾았다면 0이 갈 수 있는 4방향을 모두 탐색해본다.

범위를 벗어나지 않는다면 해당 방향에 있는 숫자와 0의 위치를 바꾼 후 next퍼즐 비트에 저장한다.

이때 같은 비트를 중복해서 탐색하지 않도록 set을 활용해서 visited 배열을 구성했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
 
typedef long long ll;
#define pli pair<ll, int>
 
using namespace std;
 
 
ll start, answer, offset = 15;
ll Checker[9];
set<ll> Check;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
 
void input(){
    ll a;
    for(int i = 0; i < 9; i++){
        cin >> a;
        a = (a << i*4);
        start += a;
    }
    
    for(ll i = 1; i <= 9; i++){
        answer += (i % 9 << (i-1)*4);
    }
    
    for(int i = 0; i < 9; i++){
        Checker[i] = (offset << i*4);
    }
}
 
int find_zero_loc(ll puzzle){
    ll k;
    for(int i = 0; i < 9; i++){
        k = Checker[i]&puzzle;
        if(k >> i*4 == 0){
            return i;
        }
    }
    return -1;
}
 
// loc1(zero)과 loc2에 있는 숫자를 swap
ll set_puzzle(ll puzzle, int loc1, int loc2){
    ll num = (Checker[loc2]&puzzle) >> loc2*4;
    
    puzzle &= ~(offset << loc2*4);
    puzzle |= (num << loc1*4);
    
    return puzzle;
}
 
void solve(){
    queue<pli > que;
    que.push({start, 0});
    Check.insert(start);
    
    while(!que.empty()){
        pli now = que.front();
        que.pop();
        
        if(now.first == answer){
            cout << now.second << "\n";
            return;
        }
        
        int zero = find_zero_loc(now.first);
        int r = zero / 3;
        int c = zero % 3;
        
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
            
            ll next = set_puzzle(now.first, zero, nr*3 + nc);
            if(Check.count(next) > 0) continue;
            
            Check.insert(next);
            que.push({next, now.second+1});
        }
    }
    
    cout << -1 << "\n";
}
 
int main(){
    input();
    solve();
    
    return 0;
}