백준 1525번 퍼즐

문제 링크입니다: https://www.acmicpc.net/problem/1525

재미있는 브루트 포스(Brute Force) + BFS(Breadth First Search) 문제였습니다.

핵심은 비어있는 칸 0을 9로 바꿔주는 것이였습니다!

알고리즘은 아래와 같습니다.

1. 3*3칸에 존재하는 숫자들을 좌상단부터 우하단까지 이어지는 숫자로 표현할 것이기 때문에 퍼즐을 입력받을 때 비어있는 칸 0을 9로 바꿔줍니다.

2. 전형적인 BFS처럼 큐에 시작하는 숫자 조합을 넣어 TARGET(123456789)이 나오거나 혹은 큐가 빌 때까지 빈 칸을 동서남북으로 swap 하며 숫자의 조합을 확인합니다.

3. TARGET이 나왔었다면 몇 번 swap했는지 출력하고 나오지 않았다면 -1을 출력해줍니다.

#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)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

 

        int start = 0; //시작할 때 순열

        for (int i = 0; i < 3; i++)

                 for (int j = 0; j < 3; j++)

                 {

                         int num;

                         cin >> num;

                        

                         //빈 칸을 9로 표시

                         if (num == 0)

                                 num = 9;

                         start = start * 10 + num;

                 }

 

        queue<int> q;

        map<int, int> visited;

        q.push(start);

        visited[start] = 0;

 

        while (!q.empty())

        {

                 int cur = q.front();

                 string s = to_string(cur);

                 q.pop();

 

                 if (cur == TARGET)

                         break;

 

                 int z = s.find('9'); //9의 위치가 비어있는 칸

                 //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 && nextY < 3 && 0 <= nextX && nextX < 3)

                         {

                                 string temp = s;

                                 swap(temp[y * 3 + x], temp[nextY * 3 + nextX]);

                                

                                 int next = stoi(temp);

                                 if (!visited.count(next))

                                 {

                                          visited[next] = visited[cur] + 1;

                                          q.push(next);

                                 }

                         }

                 }

        }

 

        if (!visited.count(TARGET))

                 cout << -1 << "\n";

        else

                 cout << visited[TARGET] << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~