1525 퍼즐 - bfs와 브루트포스 - c++

문제가 처음에 봤을땐 어떻게 풀지 감이 잘 안왔는데(bfs로 풀어야 한다는 사실 빼고)

꾸준함님 해설을 보면서 풀었다.

 

퍼즐을 아예 하나의 문자열로 받아버린 다음에 y,x 좌표를 3으로 나눈 몫과 나머지로 구한다는 사실이 꽤 신선했다.

특히 잘 익숙치 않은 메소드들을 처음 보고 아직 갈길이 멀었구나를 느꼈던 문제..

내가 몰랐다고 느낀 메소드들은 다 주석을 달아 놓았다.

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
 
const int TARGET = 123456789;
 
typedef struct {
    int y,x;
}Dir;
 
Dir moveDir[4] = {{1,0},{-1,0},{0,1},{0,-1}};
 
int main(void){
 
    int start = 0;
    for(int i=0; i<9; i++){
        int num;
        cin>>num;
        if(num==0)
            num=9;
        start = start*10+num; //이걸 하려면 0을 9로 넣어줘야 한다 꼭!
    }
 
    queue<int> q;
    map<int,int> visited; //파이썬의 dictionary 와 같은 stl.
    q.push(start);
    visited[start]=0;
 
    while(!q.empty()){
        int cur = q.front();
        string s = to_string(cur); //int to string
        q.pop();
        if(cur == TARGET)
            break;
 
        int z= s.find('9'); //비어있는 칸 저장
        int y = z/3;
        int x = z%3;
 
        for(int i=0; i<4; i++){
            int nextY = y+moveDir[i].y;
            int nextX = x+moveDir[i].x;
 
            if(0<=nextY && 3>nextY && 0<=nextX && 3>nextX){
                string temp = s;
                swap(temp[y*3+x],temp[nextY*3+nextX]); //string의 두 알파벳을 인덱스를 이용해 바꿔줌.
 
                int next = stoi(temp); //string to int
                if(!visited.count(next)){ // visited map에 next key가 없으면!
                    visited[next] = visited[cur] + 1;
                    q.push(next);
                }
 
            }
        }
    }
 
    if(!visited.count(TARGET))
        cout<<-1;
    else
        cout<<visited[TARGET];
 
 
 
}