A. 문제설명
1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. 3*3 퍼즐에 다음과 같이 수가 채워짐
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 |
2. 1~8까지 수가 주어지고 한 칸은 빈칸
3. 퍼즐의 초기 모양이 주어졌을 때, 위와 같이 정리된 상태를 만들기 위해 걸리는 이동 횟수를 구하라
B. 접근법
BFS + Map 자료구조
처음에 문제를 받아서 들었을 때, 퍼즐의 모양을 기록하여 BFS 탐사하는 방법을 생각하여 구현하였다. 하지만, 이 문제에서 주어진 메모리 제한은 32MB. 좀 더 효율적인 방법이 필요하다.
배열이 아닌 좀 더 작은 형태로 퍼즐의 스냅샷을 저장하는 방법은 스트링으로 인코딩하는 방법이다. 빈칸을 0, 나머지 1~8의 숫자를 길이 9의 문자열로 인코딩하여 큐에 삽입/추출하며 BFS 탐사하였다.
두번째로 BFS 탐사의 반복을 줄여주는 방법을 Map 자료구조를 사용한다. String -> Int 형태의 맵으로 각각의 배열 형태가 아무런 값을 가지지 않을 때는 탐사되지 않았음을, 그리고 값을 가질 때는 여태까지 탐사된 이동 횟수의 두가지 정보를 표현할 수 있다.
C. 풀이
1. 스트링 S를 입력으로 받아 정리된 상태가 될 때까지 BFS로 이동
2. 상하좌우로 이동 가능한 경우에 S의 각 문자들을 swap하며 탐사
3. 이동시 스트링 S를 Map에 마킹해주며 재탐사없도록
4. 마지막으로 목적지(123456780) 도달시 이동횟수 반환
D. 내 코드
