(C++) 백준 1525 퍼즐

문제 및 풀이

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

우와아 이풀이 감탄 나옴 ..ㅠ 처음에 일반적인 dfs로 풀었는데 깊이가 최대 8까지밖에 안들어가서 틀렸다.. 그래서 해당 풀이(https://jaimemin.tistory.com/1081) 참고해서 풀었다.

아이디어는 배열 형태의 문제를 문자열 형태로 바꿔 생각하는것
다시말해 "123456780" 의 꼴을 갖는 문자열을 만들 수 있는지 생각하면 된다.
(다만 0이 맨 앞에 오는 케이스를 위해 0을 9로 생각해서 풀었다.)

문자열로 생각하면 일반적인 bfs 문제처럼 접근해서 풀 수 있다. 어떻게 이런 생각을 할까...🥺

코드

#include <iostream>
#include <queue>
#include <map>
using namespace std;


pair<int ,int> dir[4] = {{0,1},
                         {0,-1},
                         {1,0},
                         {-1,0}};

int ans =123456789;

map<int, int> cnt;

int n, num;

int main(){

    ios_base::sync_with_stdio(0), cin.tie(0);

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
          cin>>n;
          if(n==0) n=9;
          num*=10; num+=n; 
        }
    }

    queue<int> q;
    q.push(num);
    cnt[num]=0; // 정의 필수 

    while(!q.empty()){

        int now = q.front();
        q.pop();
        if(now==ans) break;

        string tmp = to_string(now);

        int pos = tmp.find('9');
        int y = pos/3;
        int x = pos%3;

        for(int k=0; k<4; k++){

            int nextY = y + dir[k].first;
            int nextX = x + dir[k].second;

            if(nextY<0 || nextY>=3 || nextX<0 || nextX>=3) continue;

            string next = tmp;
            swap(next[nextY*3+nextX], next[y*3+x]);
            int next_int = stoi(next);

            if(!cnt.count(next_int)){
                cnt[next_int] = cnt[now]+1;
                q.push(next_int);
            }
        }

    }


    if(cnt.count(ans)) cout<<cnt[ans];
    else cout<<"-1";


}