백준 1525 퍼즐

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

1525번: 퍼즐

bfs를 통해 푸는 문제였습니다.

초기상태를 고려하지않고 가능한 모든 퍼즐의 상태를 고려해보면 9!이므로 O(362800)인것을 알 수 있습니다.

따라서 우리는 초기상태에서 목표상태로 도달할때까지 상태를 바꿔보면 됩니다. brute force 탐색 중

최단경로를 찾는데에는 bfs가 적절합니다.

이제 남은건 현재 상태에서 중복을 체크하는 방법입니다. 메모리가 32mb로 매우 작으므로 int[3][3]배열을 

set이나 map으로 체크하기에는 용량이 부족할 것으로 추측하고 현재 상태를 하나의 정수로 기록해서 

set을 통해 중복을 체크했습니다. 퍼즐의 좌상부터 우하까지 순서대로 정수의 자릿수로 기록하여 중복을 체크하여 풀었습니다.

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
set<long long> s;
int arr[3][3];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main(){
    fast_io();
    int solve=-1;
    long long a=100000000;
    long long b=0;
    for(int x=0;x<3;x++){
        for(int y=0;y<3;y++){
            long long input;
            cin>>input;
            b+=a*input;
            a/=10LL;
        }
    }
    queue<pair<long long,int>> Q;
    Q.push({b,0});
    s.insert(b);
    while(!Q.empty()){
        int now=Q.front().first;
        int dist=Q.front().second;
        if(now==123456780){
            solve=dist;
            break;
        }
        Q.pop();
        pair<int,int> zxy;
        for(int y=0;y<3;y++){
            for(int z=0;z<3;z++){
                arr[y][z]=now%10;
                if(now%10==0){
                    zxy={y,z};
                }
                now/=10;
            }
        }
        for(int x=0;x<4;x++){
            int cx=zxy.first+dir[x][0];
            int cy=zxy.second+dir[x][1];
            if(cx<0 || cy<0 || cx>=3 || cy>=3) continue;
            arr[zxy.first][zxy.second]=arr[cx][cy];
            arr[cx][cy]=0;
            a=1;
            b=0;
            for(int y=0;y<3;y++){
                for(int z=0;z<3;z++){
                    b+=a*(long long)arr[y][z];
                    a*=10LL;
                }
            }
            arr[cx][cy]=arr[zxy.first][zxy.second];
            arr[zxy.first][zxy.second]=0;
            if(s.find(b)==s.end()){
                Q.push({b,dist+1});
                s.insert(b);
            }
        }
    }
    cout<<solve;
}