[백준 1525] 퍼즐 (BFS) (C/C++) (★★)

#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
 
string startNum;
string endNum = "123456780";
bool flag = false;
 
queue<string> q;
map<string, int> visited;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < 3 && y >= 0 && y < 3)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS()
{
    visited[startNum] = 1;
    q.push(startNum);
    
    while(!q.empty())
    {
        string num = q.front();
        q.pop();
 
        if(num == endNum)
        {
            flag = true;
            return;
        }
        
        // 빈칸(0)을 찾는 반복문 
        int empty;
        for(int i = 0; i < 9; i++)
        {
            if(num[i] == '0')
            {
                empty = i;
                break;
            }
        }
        
        int x = empty / 3;
        int y = empty % 3;
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1)
            {
                string tempNum = num;
                
                // swap
                char temp = tempNum[3*x+y];
                tempNum[3*x+y] = tempNum[3*xpos+ypos];
                tempNum[3*xpos+ypos] = temp;
                
                if(visited[tempNum] == 0)
                {
                    visited[tempNum] = visited[num]+1;
                    q.push(tempNum);
                }
            }    
        }    
    }
}
 
int main(void)
{
//    freopen("B1525_input.txt", "r", stdin);
    
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            string input;
            cin >> input;
            
            startNum += input;
        }
    }
    
    BFS();
    
    if(flag == true)
    {
        cout << visited[endNum]-1 << endl;
    }
    else
    {
        cout << "-1" << endl;
    }
    
    return 0;
}