[LeetCode] 773. Sliding Puzzle

https://leetcode.com/problems/sliding-puzzle/description/

leetcode - Sliding Puzzle

문제 유형: bfs

문제 난이도: Hard

 

문제

On an 2 x 3 board, there are five tiles labeled from 1 to 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given the puzzle board board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

 

2 x 3의 보드에서, 다섯 개의 타일은 1에서 5까지, 남은 빈칸은 0으로 표현됩니다.

빈 칸에서 인접한 칸과 스왑하는 이동을 할 수 있습니다.

만약 보드가 [[1,2,3], [4,5,0]]이면, 보드가 solved되었다고 합니다.

퍼즐 보드 board가 주어집니다.

최소 몇 번의 움직임으로 해결되는지를 구하시오.

불가능하면 -1을 반환하시오.

 

풀이

bfs로 해결할 수 있다. 현재 위치를 보드의 상태를 문자열로 표현한 것으로 하면 된다.

[[1,2,3], [4,0,5]]는 상태 "123405"로 표시 할 수 있다.

즉, 최종적으로 도달해야 하는 상태는 "123450"이 된다.

 

bfs로 한 레이어씩 탐색 범위를 넓히면서, "123450"상태에 도달하면 그 탐색 레이어 수를 반환하면 된다.

map을 이용해서 문자열-부울의 꼴로 방문형태를 저장하면 된다.

다음 갈 수 있는 상태는 0의 위치로 정한다.

0이 어디와 스왑할 수 있는지는, 2 x 3이니 정해진 테이블을 만들어낼 수 있다.

이를 이용해서 다음 가능한 상태의 문자열을 만들어낼 수 있다.

 

가능한 모든 문자열 상태에 방문하고도 도달하지 못하면, -1을 반환해주면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int _ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    string getState(vector<vector<int>>& board) {
        string state = "";
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 3; ++j) {
                state += board[i][j] + '0';
            }
        }
        return state;
    }
    int slidingPuzzle(vector<vector<int>>& board) {
        unordered_map<int, vector<int>> moves = {
            {0, {1, 3}},
            {1, {0, 2, 4}},
            {2, {1, 5}},
            {3, {0, 4}},
            {4, {1, 3, 5}},
            {5, {2, 4}}
        };
        unordered_map<string, bool> visited;

        string first = getState(board);
        string target = "123450";
        visited[first] = true;

        queue<string> q;
        q.push(first);

        int times = 0;
        while(!q.empty()) {
            int qsize = q.size();
            for(int i = 0; i < qsize; ++i) {
                auto curr = q.front();
                q.pop();

                if(curr == target) return times;

                int pos0 = -1;
                for(int j = 0; j < 6; ++j) {
                    if(curr[j] == '0') {
                        pos0 = j;
                        break;
                    }
                }
                auto nextMoves = moves[pos0];
                for(int next : nextMoves) {
                    string nextState = curr;
                    swap(nextState[next], nextState[pos0]);

                    if(!visited[nextState]) {
                        visited[nextState] = true;
                        q.push(nextState);
                    }
                }
            }
            times++;
        }

        return -1;
    }
};