[백준 1525] 퍼즐

 

매우 참신한 문제이다. 

처음에는 메모리 제한이 적길래 bfs를 쓰지 말라는 건 줄 알았는데 이후 문제를 읽다 보니 그런 문제가 아니었다. 

풀이 방법

1. 입력을 나중에 방문 처리하기 유리하게 하나의 int로 받는다.
   • 여기서 0은 9로 변경하여 받는다.
     • 왜냐하면 012345678처럼 0이 맨 앞에 오는 경우에는 int로 처리했을 때 12345678이 되기 때문에 9자리 숫자가 아니라 8자리 숫자가 된다.
2. 방문 체크는 map을 이용한다.
   • map을 사용하지 않으면 매번 찾아야 된다. index를 따로 저장하기보다는 map을 사용하여 한번에 찾는 것이 유리하다. 
3. 현재 9(원래 0)의 위치는 string으로 변환한 뒤 find 하여 찾는다.
   • string으로 변환한 이유는 0의 위치를 쉽게 찾기 위해서이다. string에서 기본적으로 제공해주는 기능을 사용하기 위해 사용하였다.
4. 나머지는 평범한 bfs와 동일하다. 종료 조건을 123456789와 동일할 때로 주고 그때의 최소 거리를 map에서 가져온다.
   • bfs를 사용한 이유는 퍼지면서 최초 방문한 게 최소 거리기 때문에 여기서 적합하다.

 

소스코드

#include <stdio.h>
#include <map>
#include <algorithm>
#include <queue>
#include <string>
#include <iostream>
#define GOAL 123456789
using namespace std;
 
map<int, int> distances; //퍼즐 각모양별 최소 distances
queue<int> q;
int dir_row[4] = { 1,0,-1,0 };
int dir_col[4] = { 0,-1,0,1 };
 
bool isRange(int r, int c) {
    if (r < 0 || r >= 3 || c < 0 || c >= 3)
        return false;
    return true;
}
 
void bfs() {
    while (!q.empty()) {
        int state = q.front();
        //cout << q.size()<<","<<distances.size()<< endl;
        q.pop();
        if (state == GOAL) {
            printf("%d\n", distances.find(state)->second);
            return;
        }
        string str = to_string(state);
        int cur_pos = str.find('9');
        int row = cur_pos / 3;
        int col = cur_pos % 3;
        for (int i = 0; i < 4; i++) {
            int next_row = row + dir_row[i];
            int next_col = col + dir_col[i];
            if (isRange(next_row, next_col)) {
                int next_pos = next_row * 3 + next_col;
                string next_state_str = str;
                swap(next_state_str[cur_pos], next_state_str[next_pos]);
                int next_state = stoi(next_state_str);
                auto cur_dist = distances.find(state)->second;
                auto iter = distances.find(next_state);
                if (iter == distances.end()) { //방문체크
                    distances.insert(make_pair(next_state, cur_dist + 1));
                    q.push(next_state);
                }
            }
        }
    }
    printf("-1\n");
}
 
int main() {
    int puzzle = 0;
    for (int i = 0; i < 9; i++) {
        int input;
        scanf("%d", &input);
        if (input == 0)
            input = 9;
        puzzle = puzzle * 10 + input;
    }
    distances.insert(make_pair(puzzle, 0));
    q.push(puzzle);
    bfs();
}

 

 

 

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

1525번: 퍼즐