BOJ 1525 - 퍼즐

링크: https://www.acmicpc.net/problem/1525

비트마스크로 해결하는 BFS이다.

3*3 퍼즐을 123 456 780 의 9자리 정수로 본다. 여기서 123456780이 문제에서 말하는 정리된 상태, 즉, 목표이다.

각 칸마다 퍼즐을 이동 시킬 수 있는 주변 4방향이 다르다. 

구현하는 방법은 각 칸마다 인접 리스트를 만들거나, 행렬로 표현하든지 if문으로 하는 등 다양하다. 아래 코드에서는 반대로 이동이 불가능한 방향을 저장해서 구현했다.

문제는 "123456780" 과 같은 상태를 방문 했는지 여부를 확인하기에는 visit[876543210]를 수용할 수 있는 배열 크기가 필요하다. 하지만 실제로 나타날 수 있는 상태의 개수는 \(9! = 362,880\) 이다. 방문했음을 저장하기 위한 적절한 자료구조가 필요하다.

C++ STL에서는 삽입과 삭제, 조회가 \(O(lgN)\)에 가능한 set과 map이 있다. 직접 구현해야 하는 상황이 아니라면 STL을 사용하면 간단해진다.

또는 퍼즐의 상태에서 나타나는 각 자리가 8을 넘지 않으므로 9진수로 변환하면 배열로 커버가능하다. \(9^9 = 387,420,489\) 이기 때문에 적당한 자료형의 배열과 원소의 비트를 활용하면 메모리 제한 내에 해결할 수 있다.
이 트릭에 대해서는 BOJ 13701 - 중복 제거와 BOJ 15719 - 중복된 숫자를 풀어보면 좋다.

코드