[LeetCode] 773. Sliding Puzzle - Python

 

 

난이도: 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.

 

문제 예제

---

Example 1:

 

Input: board = [[1,2,3],[4,0,5]]

Output: 1

Explanation: Swap the 0 and the 5 in one move.

 

Example 2:

 

 

Input: board = [[1,2,3],[5,4,0]]

Output: -1

Explanation: No number of moves will make the board solved.

 

Example 3:

 

Input: board = [[4,1,2],[5,0,3]]

Output: 5

Explanation: 5 is the smallest number of moves that solves the board.

An example path:

After move 0: [[4,1,2],[5,0,3]]

After move 1: [[4,1,2],[0,5,3]]

After move 2: [[0,1,2],[4,5,3]]

After move 3: [[1,0,2],[4,5,3]]

After move 4: [[1,2,0],[4,5,3]]

After move 5: [[1,2,3],[4,5,0]]

 

제한 사항

---

• board.length == 2
• board[i].length == 3
• 0 <= board[i][j] <= 5
• Each value board[i][j] is unique.

 

✏️ Solution(솔루션)

---

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        want_result = [[1,2,3],[4,5,0]]
        visited = defaultdict(bool)

        for i in range(2):
            if 0 in board[i]:
                start_x = i
                start_y = board[i].index(0)
                break
        
        moves = [[0,1], [1, 0], [0,-1], [-1,0]]
        visited[tuple(board[0] + board[1])] = True
        q = deque([[start_x, start_y, 0, deepcopy(board)]])

        while q:
            x, y, cnt, now_board = q.popleft()
            if now_board == want_result:
                return cnt

            for move in moves:
                nx = x+move[0]
                ny = y+move[1]

                if 0 <= nx < 2 and 0 <= ny < 3:
                    now_board[x][y], now_board[nx][ny] = now_board[nx][ny], now_board[x][y]

                    if not visited[tuple(now_board[0] + now_board[1])]:
                        visited[tuple(now_board[0] + now_board[1])] = True
                        q.append([nx, ny, cnt + 1, deepcopy(now_board)])
                    
                    now_board[x][y], now_board[nx][ny] = now_board[nx][ny], now_board[x][y]

        return -1

 

이 문제는 board안에 0과 인접한 상하좌우 요소랑 서로 바꾸면서 board가 [[1,2,3],[4,5,0]]이 될 수 있는 최소한의 움직임을 반환하면 되었다.

 

나는 이 문제를 bfs로 접근하여 풀었다.

 

시작 위치를 0의 위치로 잡고 상하좌우 요소랑 바꾸면서 board를 업데이트 했다.

바뀐 0의 위치랑 업데이트된 board를 deepcopy함수를 통해 q에 넣었고, board의 길이는 2니까 visited 확인은 tuple(board[0] + board[1])과 같이 check했다.

visited는 다음과 같이 저장이 된다. → (1,2,3,4,0,5): True

 

이러한 작업을 반복하다가 q에 저장되어있던 now_board가 [[1,2,3],[4,5,0]]와 같다면 현재까지의 움직인 수를 반환했다.

 

만약 while q: 반복문을 빠져나가면 [[1,2,3],[4,5,0]]를 만들 수 없다고 판단해 -1을 반환했다.

 

이 문제는 BFS를 사용해야겠다고 생각만 한다면 쉽게 풀 수 있는 문제 같다.

문제를 읽고 문제가 원하는 알고리즘이 무엇인지 잘 생각해야할 것 같다.

---

[LeetCode] 773. Sliding Puzzle