38. State Space, 15 Puzzle [14-2주차]
2024년
1월 14일 일요일
오후 5:17
<State Space>
모든 가능한 상태들의 집합을 State Space라
한다.
<15 Puzzle>
15 Puzzle은 빈칸과 빈칸 상하좌우에 위치한 숫자의
자리를 바꿔 가며 숫자들이 순서대로 배열되게 만드는 방법을 구하는 문제이다. (빈칸과 빈칸 상하좌우
방향으로 1칸 떨어진 4개의 숫자들과만 자리를 바꿀 수 있다)
여기서 State Space는 모든 가능한 숫자
배열의 집합이다. State Space의 원소 개수는 총 16!이
된다.
<15 Puzzle에서의 State Space Graph>
State Space를 그래프로 표현한 것을 State Space Graph라 한다.
15퍼즐에서 State
Space Graph의 노드들은 16!가지의 숫자 배열이고, 간선은 빈칸을 한번 움직여서 서로를 만들 수 있는 노드를 잇게 된다.
State Space Graph를 만든 뒤, Dijkstra알고리즘으로 입력과 정답 간의 최단 거리를 구하면 15
Puzzle문제가 풀린다.
<15 puzzle의 정답이
없는 경우>
15 puzzle에서
State Space Graph는 두 개의 Connected Component를 갖는다. 하나의 노드에 대해, 반대쪽
Connected Component에 특정 노드의 두 개의 숫자 자리를 서로 바꾼 상태가 있다.
이는 15 puzzle에서 정답을 절대 만들 수
없는 경우가 있다는 말을 포함한다. 정답이 맞춰진 상태에서, 빈칸이
아닌 두 숫자의 자리를 서로 바꾸면 절대로 정답으로 만들 수 없다.
증명은 다음과 같다.
15 퍼즐에 배열된 숫자들을
1차원 배열에 저장한다. (빈칸은 16으로 치고
저장한다)
그리고 다음과 같이 용어들을 정의한다.
- Permutation : 배열의
특정 숫자 오른쪽에 존재하는 자신보다 작은 숫자의 개수
- ∑P : 16개 숫자의 Permutation 합
- Distance : 퍼즐에서 16과 오른쪽 아래 구석까지의 수평+수직 거리.
임의의 두 숫자의 자리를 서로 바꾸면 (∑P % 2) 의 값(∑P의
홀수 짝수 여부)이 바뀐다.
- 증명 : a<b이고, b가 a보다 오른쪽에 있을 때, 숫자 a와 b의
자리를 바꾼다고 하자. 이때 고려해야 할 것은 a와 b의 자리 사이에 있는 숫자들이다. 사이에 있는 숫자들은
숫자의 크기에 따라 세 종류로 구분된다.
- a보다
작은 숫자들이 k개이면 : a의 permutation이 k만큼 줄어든다. b의 permutation은 k만큼 증가한다.
- b보다
큰 숫자들이 i개이면 : 이 i개의 숫자들은 a와 b의 permutation에 영향을 미치지 않는다.
- a보다
크고 b보다 작은 숫자들이 t개이면 : a의 permutation값에는 영향을 미치지 않고, b의 permutation 값은 t만큼 증가한다. 또한
t개의 숫자 각각의 permutation 값이
1씩 증가한다.
- 마지막으로, a와 b 두 숫자만 고려하면, b의 permutation이 a에 의해 1증가한다.
따라서 ∑P값은 2t+1만큼 증가한다.
a>b인 경우는 바꾼 두 숫자의 위치를 원래대로 되돌리는 경우를 생각하면 된다.
따라서 16이 아닌 두 숫자를 서로 바꾸면 (∑P + distance) % 2의 값이 바뀌게 된다.
그러나 문제에서 허용된 방법으로 두 숫자를 서로 바꾸는 경우, 즉 16과 그 상하좌우 4개
숫자 중 하나의 자리를 바꾸는 경우, ∑P % 2의 값도
바뀌지만 distance % 2의 값도 바뀌기 때문에 (∑P + distance) % 2 의 값은 그대로이다.
정답인 상태에서는 (∑P + distance) % 2 = 0 이다. (∑P + distance) % 2 = 1인 경우 정답으로 만들 수 없게 된다.
State space graph의 두 개의 connected component가 서로 분리되어 있다는 것은 증명되었다.
connected component 각각이 연결된 상태라는 것의 증명은 너무 복잡하므로 생략한다.
OneNote에서 작성되었습니다.