백준 1525 - 퍼즐

백준 1525 - 퍼즐

한 군데가 비어있는 퍼즐을 오름차순으로 배치하는 최소 횟수를 찾는 문제다.

비어있는 위치를 9라고 하면

1 2 3

4 5 6

7 8 9

의 형태로 퍼즐을 만드는 문제로 바꿀 수 있다.

그리고 이를 일렬로 나열하면 일직선 퍼즐을 123456789로 만드는 문제로 바꿀 수 있다.

퍼즐의 각 위치에서 이동할 수 있는 곳에 에지를 연결하면서 그래프 모델링을 하자.

그러면 현재 퍼즐의 상태가 주어졌을 때 숫자가 9인 노드는 연결된 노드의 숫자와 swap 할 수 있다는 의미가 된다.

123456789를 기준으로 9는 6, 8과 swap이 가능하다. 즉 9가 위치한 노드와 연결된 노드의 숫자를 서로 바꾸는 경우를 모두 탐색하면 최종 9! 의 경우의 수를 살펴보게 된다.

9! 의 경우는 그다지 큰 경우가 아니므로 BFS의 사용을 고려할 수 있다.

BFS를 어떻게 해야 하는지 고민이 있을 수 있는데 저렇게 일직선으로 바꾼 퍼즐을 스트링으로 처리하면 된다.

예제 TC1의 경우에는 "193425786"이 된다. 0을 9로 바꿨음을 잊지 말자.

그러면 BFS를 수행하는 큐에는 퍼즐의 상태를 나타내는 스트링이 들어가게 되며 각 원소마다 9가 위치한 노드와 연결된 노드들을 swap 해가며 최적의 경우를 탐색하면 된다.

각 상태에 도달하기 위한 최소 횟수를 map로 관리할 수 있으며 count()가 false 거나 mp[current] + 1 < mp[next_string] 이면 이를 map에 반영, 큐에 삽입해서 간단하게 구현할 수 있다.

BFS가 끝난 뒤 map에 "123456789"가 존재하면 해당 value 출력, 없으면 -1을 출력하면 정답을 받을 수 있다,

자세한 구현은 밑 코드를 참조한다.

전체 코드

from http://nicotina04.tistory.com/179 by ccl(A) rewrite - 2021-11-04 04:00:56