[백준 #1525] 퍼즐

개요

---

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

1525번: 퍼즐

bfs로 풀었다.

비트마스크로도 풀 수 있다고 한다. 나중에 비트마스크 공부하면서 다시 봐야지!

 

메모리가 엄청 빡빡하더라. 36MB? 이런건 처음봤다. 보통 256MB이렇게 주는데.

상태공간을 벡터로 넣으면 그정도 쓰나?

그냥 int로해도 876543210 (약 8억) < 2^31-1 (약 20억)이라서, int범위 안에 들어가길래 그냥 int로 바꿔서 넣었다.

visited도 vector로 하면 느려서 unordered_set을 넣었다. 일반 set은 O(logn)인데 unordered_set은 O(1)이다. 대단해!

 

숫자의 특정 자리수끼리 바꾸는건 저번에 #1963_소수경로에서 배운것처럼 string으로 처리하면 편리하다.

n%10 * 10어쩌구저쩌구 이럴필요없이 그냥 to_string과 stoi로 해결하자!

 

코드 (정답, 9376KB, 120ms)

---

/**
 * @name: 퍼즐
 * @link: https://www.acmicpc.net/problem/1525
 * @date 2020-05-05
 * @author sunmon
 * TIP: 
**/
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_set>
using namespace std;

int di[4] = {-3, -1, +3, +1};  // ↓ → ↑ ←
unordered_set<int> visited;
queue<pair<int,int> > q; //num, dist

void push_queue(string& str, int idx, int dist, int flag){
    iter_swap(str.begin()+idx, str.begin() + idx + di[flag]);
    int i = stoi(str);
    if(visited.find(i)==visited.end()){
        visited.insert(i);
        q.push({i, dist+1});
    }
    iter_swap(str.begin()+idx, str.begin() + idx + di[flag]);
}

int solve(int n){
    int dest = 123456780;

    q.push({n,0});

    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();

        if(cur.first == dest) return cur.second;
        string str = to_string(cur.first);
        int idx = str.find('0');
        if(idx == -1){
            str = "0" + str;
            idx = 0;
        }

        //위->아래로 옮기기
        if(idx>=3) push_queue(str,idx,cur.second,0);

        //왼쪽->오른쪽으로 옮기기
        if(idx%3) push_queue(str, idx, cur.second,1);

        //아래->위로 옮기기
        if(idx+3<9) push_queue(str, idx, cur.second,2);

        //오른쪽->왼쪽으로 옮기기
        if((idx+1)%3) push_queue(str, idx, cur.second, 3);
    }

    return -1;
}
int main(){
    int n=0;
    for(int i = 0; i<9; i++){
        int m;
        cin >> m;
        n = n*10+m;
    }
    cout << solve(n);
}