[문제분석/해석] n-puzzle 최소이동 횟수 알고리즘 구하기(이미지 추가)

해당 포스팅 글은 

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 0 5

7 8 6 

 

1 2 3

4 5 6

7 8 0

 

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있었다. 

이와 같이 최소 이동 횟수를 구하라. 

 

예제 입력 

3

 

 1 0 3

4 2 5

7 8 6

 

예제 출력

3

 

 

문제 분석

---

위 문제를 보고 다음과 같이 핵심적인 내용 / 부가적인 내용에 대해 정리했다.

 

 

 

 

문제 해결을 위한 접근 방법 

---

다음과 같이 3step에 걸쳐 문제 접근 방법을 소개하겠다. 

 

 

Step1. 퍼즐 문제 풀기

실제 앱을 설치하여 규칙을 찾아보려고 했다. 

NumPuz라는 앱을 깔면 문제를 풀 수 있다. 

 

 

그리고 내가 발견한 규칙은 1을 최상단 왼쪽 그리고 2, 3을 오른쪽에 배치한다는 것이다.

이 방법으로 4도 중단 왼쪽에 맞추고 5, 6을 오른쪽에 배치하면 모든 문제를 빠르게 풀 수 있다.

 

 

하지만 이 풀이 법에는 문제가 있었다.

 

 

핵심 조건인 최소 이동횟수를 구할 수 없었기 때문이다.

 

 

 

 

Step2. insert Sort / Merge Sort를 통해 문제 접근 

주어진 2차원 배열을 1차원 배열로 만들어서 정렬을 하면 그 이동하는 숫자가 정답이 되지 않을까? 란 생각으로 문제를 접근했다.

 

 

 

merge sort / insert sort는 정렬 방법 중 하나인데.

정렬 알고리즘에 대해서 어렵지 않으니 따로 찾아보기 바란다.

 

 

아무튼 다시 문제로 돌아와서 insert sort를 사용하던, merge sort를 사용하던 문제를 해결할 수 없었다.

그 이유는 정렬을 통해 최소 이동횟수를 구할 수 있었지만,

0과 인접한 숫자들만 움직일 수 있다는 조건을 만족시키지 못했기 때문이다.

 

 

그래서 2차원 배열을 1차원 배열로 바꾸고 문제를 푼다는 것은 불가능하다고 판단했다.

 

 

우리는 앞의 Step1과 Step2를 통해 다음과 같이 알게 되었다.

1차원 배열이 아닌 2차원 배열이어야하고, 

2차원 배열의 전체를 돌아다니면서 최소의 이동수를 구해야 한다.

 

 

 

그렇다면 전체를 탐색하면서 어떻게 최소 이동 횟수를 구할 수 있을까?

 

 

 

Step3. 0의 위치를 통한 거리 계산

우리에게 중요한 단서가 되는 0과 인접한 숫자들만 움직일 수 있다는 정보이다.

 

 

* 이 문제의 핵심 - 꼭 이해하고 넘어가자.

1. 초기 상태인 0의 현재위치를 알아야 하며

2. 0의 위치에서 이동할 수 있는 위치를 알아야 하며 (바깥 제외)

3. 0이 이동하면서 생성되는 새로운 퍼즐과 

4. 목표상태가 되기 위해 퍼즐 내부에서 변해야 하는 숫자가 최소인 경우가 

5. 최소 이동 거리라고 판단했다.

 

 

위 글이 잘 이해가 안 가면 다음 그림을 보자.

 

초기 상태 0의 위치에서 

0이 이동하면서 만들 수 있는 0의 퍼즐 모양은 새로운 퍼즐(1)과 같다.

새로운 퍼즐(1)의 모양과 목표상태의 퍼즐 모양을 비교한다.

새로운 퍼즐(1)에서 0이 가운데 위치해 있을 경우 5, 6의 숫자만 퍼즐에서 놓인 위치가 다르다.

최소 숫자가 2개로 0이 퍼즐의 가운에 있을 경우 목표 상태에 도달할 수 있는 경우가 제일 빠르다.

 

이 과정을 반복한다.

0이 가운데에 위치한 새로운 퍼즐에서 0이 갈 수 있는 경우를 찾는다. 

이때 0의 위치가 오른쪽으로 갈 경우 목표상태와 비교해서 바뀌어야 하는 숫자는 6 하나로 가장 짧은 이동거리라고 볼 수 있다.

 

*여기서 중요한 문제

1. 자신이 갔던 이전의 0의 위치로 갈 수 없다.

2. 새로운 퍼즐(2)에서 목표상태가 되기 위해 바뀌어야 하는 숫자가 2개 이상이 나올 수 있다.
(로직에서 PriorityQueue를 통해 해결하면 된다.)

 

2번에 대한 내용은 예제 이미지를 참고하자.

 

위 이미지와 같이 동일한 숫자가 나올 경우에 대해서 해결해줘야 한다.

 

그러고 나서 반복하면 문제를 해결할 수 있다.

 

 

 

풀 수 없는 퍼즐의 존재

---

 

입력 값으로 주어진 숫자가

 

1 0 3

4 2 5

7 8 6

 

가 아닌 다른 입력값이 주어질 경우 퍼즐이 만들 수 없는 경우가 발생한다.

왜 만들 수 없는 퍼즐의 경우가 발생할까? 

 

다음 예시를 살펴보자.

 

2 x 2 퍼즐의 예시 

퍼즐을 좋아하는 금쪽이가 2 x 2 퍼즐을 구매했다.

 

 

2 x 2 퍼즐에서 만들 수 있는 모양은 다음과 같다. 

 

 

 

활발한 금쪽이가 2 x 2 퍼즐을 가지고 놀다가 퍼즐을 떨어트렸고, 퍼즐의 모양이 다음과 같이 변했다.

0 2 

3 1

 

 

금쪽이는 퍼즐을 기존의 

1 2

3 0

모양으로 맞출 수 있을까?

 

 

정답은 x이다.

 

 

위 그림을 보면 알 수 있듯이

 

1 2 

3 4

에서 만들 수 있는 모양 중

 

0 2

3 1

의 모양은 없기 때문이다.

 

 

역전 카운트에 대해

이 글을 보고 있는 우리는 n x n 퍼즐의 문제를 찾아보다가 역전 카운트라는 단어를 들어보았을 것이다. 

역전 카운트란 자신보다 앞에 있는 수 중에 자신보다 큰 수를 찾고 싶을 때를 의미한다.

 

 

각각의 역전 카운트는 다음과 같다.

목표 퍼즐의 역전 카운트는 항상 정렬되어 있기 때문에 역전카운트는 0이다.

초기 퍼즐의 역전 카운트는 1이 2와 3 앞으로 와야 하기 때문에 역전카운트는 2이다.

 

우선 나의 경우는 역전카운트가 홀 수 일 경우 절대 퍼즐을 풀 수 없을 것이라고 접근을 했다.

왜냐하면 목표 퍼즐의 역전카운트가 짝수개(0) 이기 때문에 초기 퍼즐의 역전 카운트 또한 짝수여야 목표 퍼즐의 모양을

만들 수 있을 것이라고'만' 생각했다.

 

하지만 다음과 같이 목표퍼즐의 역전카운트가 0 초기 퍼즐의 역전카운트가 2여도 풀 수 없는 경우가 발생했다.

 

왜 이런 경우가 발생할까?

우선 2 x 2의 퍼즐이 만들 수 있는 경우의 수는 몇일까? 

한 번 생각해 보자.

 

정답은 (2 * 2)!로 

4 * 3 * 2 * 1 = 24개의 경우의 수가 나온다.

하지만 위의 그림을 다시 보면 

 

1 2

3 0 

퍼즐로 만들 수 있는 경우의 수는 12개이다.

 

나머지 12개의 퍼즐은 어디로 사라졌을까?

이렇게 짝수 퍼즐의 경우는 위와 같은 모양을 가진다.

그래서 다음과 같은 공식을 대입해야 한다.

 

 

이와 관련해서는 수학적으로 접근해야 하는데 궁금한 사람이 있다면 아래 영상을 참고하자. (과학고 최고)

https://www.youtube.com/watch?v=uxj1MqhRDFQ 

 

 

정리

---

 

지금까지의 내용을 정리해보자.

지금까지 우리는 다음과 같은 과정을 거쳐왔다

이번 포스팅 글에서 2가지만 기억하자.

 

풀 수 있는 퍼즐 검사하기.

0의 위치를 확인하며 퍼즐 비교하기.

 

이런 과정을 통해 문제를 풀어본다면  정답을 얻을 수 있다. 

 

그리고 0이 이동한 위치를 통해 목표로 하는 상태와 비교하면서

최선의 판단을 하며 나아가는 것을 휴리스틱이라고 하며

휴리스틱 개념을 통해 구현된 것이 A* 알고리즘이다.

 

이번 포스팅에서는 바로 A* 알고리즘을 알고 문제를 해결하는 것 보다.

n-puzzle의 문제를 분석하고, 어떻게 접근해야 하는지 알아보았다.

 

A*가 왜 나왔으며, 어떤 과정을 통해 발전되었는지 이번 포스팅 글을 통해 알게 되었으면 좋겠다. 

 

 

 

 

---

이미지랑 설명들을 정말 열심히 준비했습니다....ㅠㅠ

도움이 되었다면 댓글..부탁합니당❤️

큰 힘이 됩니다 ㅎㅎ