개발 개맛집

해당 포스팅 글은 n-puzzle을 풀기 위한 문제 분석과 접근 방법에 대한 글이다. 문제를 해결하기 위한 알고리즘 풀이에 대한 내용이 아니다. 이미 알고리즘에 대한 내용은 인터넷에 많으니 이번 글에서는 문제를 해석하고 접근하는 과정을 알아보자. 문제 문제 내용 슬라이딩 퍼즐이 있다. 다음과 같은 수가 주어질 때 오른쪽 가장 끝 칸은 비어있는 칸이다. 1 2 3 4 5 6 7 8 0 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있다면, 수를 그 칸으로 이동시킬 수 있다. 물론 표 바깥으로 이동할 수 없다. 우리의 목표는 초기 상태가 주어졌을 때 최소의 이동으로 위와 같은 정리된 표를 만드는 것이다. 다음 예를 보자. 1 0 3 4 2 5 7 8 6 1 2 3 4 0 5 7 8 6 1 2 3 4 ..