[LeetCode] 773. Sliding Puzzle

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

Sliding Puzzle - LeetCode

문제

2 x 3 보드에는 1에서 5까지 레이블이 지정된 5개의 타일과 0으로 표시되는 빈 사각형이 있습니다. 이동은 0과 4방향으로 인접한 숫자를 선택하고 교체하는 것으로 구성됩니다. 보드의 상태는 보드가 [[1,2,3],[4,5,0]]인 경우에만 해결됩니다. 퍼즐 보드 보드가 주어지면 보드의 상태가 해결되도록 필요한 최소 이동 횟수를 반환합니다. 보드의 상태를 해결할 수 없는 경우 -1을 반환합니다.

 

접근

어렸을때 가지고 놀던 슬라이딩퍼즐을 맞추는 가장 적은 횟수를 구하는 문제이다.

 

퍼즐의 풀이방법을 구현하여서 푸는 방법도 있을 것 같고https://namu.wiki/w/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9%20%ED%8D%BC%EC%A6%90

슬라이딩 퍼즐 - 나무위키

빈 공간을 기준으로 이동알고리즘을 작성하는 방법도 있을 것 같았는데, 절차가 잘 떠오르지 않았다.

퍼즐의 배열 상태를 하나의 노드로 보고,

빈공간(0)의 이동 가능 경로의 이동 후 배열상태를 자식노드로 연결하여

전체 경우의 수를 탐색하는 방법을 쓰는 것을 방향으로 잡고 접근하였다.

구현에 사용한 변수는 다음과 같다.

 

목표 퍼즐상태 String = "123450"

현재 상태 String

방문노드 캐시용 HashSet<String>

탐색노드 저장용 Queue

퍼즐의 위치 별 탐색 가능 방향 배열 int[][]

 

의사코드

1. 초기값 세팅

2. 탐색용 배열과 캐시에 현재상태 세팅

3. 노드 탐색(큐가 빌 때까지){

    1. 탈출조건 체크 ( 탐색깊이 반환 )

    2. 현재 0의 위치 확인

    3. 가능한 이동방향 퍼즐상태 저장(0 <-> 목표 스왑)

        1. 캐시확인, 방문노드면 큐에 저장X

        2. 미방문 노드면 큐에 저장

    4. 탐색깊이 ++

}

4. 탐색 실패 시 -1 반환