[백준 1525번] [BFS] 퍼즐

Approach

최소 이동 횟수를 물어보는 지점에서 BFS 문제를 추측할 수 있다. 

이 경우에는 이동하는 기준이 3 x 3 상태이다. 따라서 해당 3 x 3 배열을 일종의 정점처럼 취급하여 BFS를 돌리면 된다.

(0의 위치를 기준으로 탐색을 해도 된다는 생각이 들 수 있으나, 0의 위치가 같아도 행렬이 달라질 수 있기 때문에 이 방법으로는 이 문제를 풀 수 없다.)

 

다만, 배열을 직접적으로 넣으면 메모리 초과에 걸리므로 string 자료형을 활용하여서 메모리를 상당히 줄였다.

 

BFS에 들어가는 정보가 좌표가 아니라 배열이라는 점이 매우 독특했던 문제이다.

(참고 : https://blog.naver.com/kks227/220785747864)

너비 우선 탐색(Breadth-First Search) (수정 2018-11-22)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
set<string> visited;

int main(void){
    string v = "";
    string end = "123456780";

    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            int t;
            cin >> t;
            v += to_string(t);
        }
    }
    int m[9][4] = {{-1, 3, -1, 1},
                   {-1, 4, 0, 2},
                   {-1, 5, 1, -1},
                   {0, 6, -1, 4},
                   {1, 7, 3, 5},
                   {2, 8, 4, -1},
                   {3, -1, -1, 7},
                   {4, -1, 6, 8},
                   {5, -1, 7, -1}};

    queue<string> q;
    q.push(v);
    visited.insert(v);

    int move_num = 0;
    bool flag = false;
    while(!q.empty()){
        int q_size = q.size();
        for(int i = 0; i < q_size; i++){
            string cur = q.front();
            if(cur == end){
                flag = true;
                break;
            }
            
            int zero_pos;

            for(int i = 0; i < cur.size(); i++){
                if(cur[i] == '0'){
                    zero_pos = i;
                    break;
                }
            }

            q.pop();

            for(int j = 0; j < 4; j++){
                string next = cur;
                int next_index = m[zero_pos][j];
                if(next_index == -1) continue;

                next[zero_pos] = cur[next_index];
                next[next_index] = cur[zero_pos];

                if(visited.find(next) == visited.end()){
                    q.push(next);
                    visited.insert(next);
                }

            }
        }
        if(flag){
            cout << move_num << "\n";
            return 0;
        }
        move_num++;

    }

    // No case exist;
    cout << -1 << "\n";
    return 0;
}