[백준 1525] 퍼즐

0. 제목

• 백준 1525 퍼즐
• BOJ 1525 퍼즐
• C++ 1525 퍼즐

---

1. 문제

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

---

2. 풀이

• 이 문제는 브루트포스와 BFS를 사용하는 문제였다.
• 아홉개의 칸 순서대로 이어지는 숫자로 표현할 것이기 때문에 0을 9로 바꿔주고 시작한다.
• 정수를 입력받으면서 start라는 변수에 9자리 수를 저장한다.
• key, value쌍을 가지고 있는 map을 사용하여 dist를 선언한다. dist[x]는 x까지 움직인 횟수를 뜻한다.
• BFS를 사용하기 위해 큐를 선언하고 큐가 빌때까지 반복한다.
• 큐의 맨 앞에 있는 정수를 문자열로 만들어준다. 그 후 pop을 하고 9가 저장되어 있는 인덱스를 찾는다.
• 찾은 인덱스를 이용하여 x좌표와 y좌표를 찾는다.
• 미로찾기와 비슷하게 상하좌우 범위를 확인하며 탐색한다.
• 탐색 할때 상하좌우 교환을 해보고 한번도 가보지 않은 길이라면 큐에 push해준다. 또한, 그곳까지의 거리도 기존 거리에서 1을 추가해준다. 가지가 뻗어나가는 것을 생각하면 된다.
• 그렇게 결국 큐가 비어서 반복문을 빠져 나오고 dist배열에서 123456789를 찾아본다. 만약 없다면, -1을 출력해주고 있다면 그곳까지 걸린 거리를 출력해준다.

---

3. 코드

#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
 
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int start = 0;
    int temp;
    
    //예시로 입력받은 것을 193425786처럼 만든다.
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> temp;
            if(temp == 0)
                temp = 9;
            
            start = start * 10 + temp;
        }
    }
    
    map<int, int> dist; //key, value쌍
    queue<int> q;
    q.push(start);//193425786
    dist[start] = 0;//처음 위치까지 움직인 수는 0(초기값)
    
    while(!q.empty()){
        int now_num = q.front();//큐의 제일 앞 원소 저장
        string now_str = to_string(now_num);//문자열로 만들어줌
        q.pop();
        
        int z = (int)now_str.find('9');//9가 저장되어 있는 Index를 찾아줌
        int x = z / 3;//x좌표는 상하
        int y = z % 3;//y좌표는 좌우
        
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;//범위 벗어나면 continue
            string next_str = now_str;
            swap(next_str[x * 3 + y], next_str[nx * 3 + ny]);//교환
            int next_num = stoi(next_str);
            
            if(dist.count(next_num) == 0){//처음 가는 길이라면
                dist[next_num] = dist[now_num] + 1;//1추가
                q.push(next_num);
            }
        }
    }
    
    if(dist.count(123456789) == 0)
        cout << "-1" << '\n';
    else
        cout << dist[123456789] << '\n';
 
    return 0;
}