반응형
1. 문제정의
위 모양의 퍼즐을 1234 순서대로 만드는것이다.
빈칸의 상하좌우 숫자들은 빈칸과 자리를 바꿀 수 있다.
2. State Space
상태공간이란, 문제가 처할 수 있는 모든 상태를 모아놓은 것이다.
모든 상태가 다 solve가능한 상태일까?
아니다. 퍼즐 두개를 뽑아서 자리를 바꾸면 풀수 없는 상태가된다.
하지만 또 두개를 뽑아서 자리를 바꾸면 풀 수 있는 상태가 된다.
state가 될 수 있는 모든 경우의수를 생각해보면 16!이다.
매우 큰 숫자이다..!
이 퍼즐에는 Invariant가 있다.
Permutation과 빈칸과 코너의 거리를 더한 값이 유지된다는 것이다.
먼저 빈칸을 16으로 생각하고 배열을 만든다.
각 숫자에 자신보다 오른쪽 중 자신보다 작은수의 개수를 적는다(Permutation)
빈칸과 떨어진 칸 수를 구한다 (16과 코너의 거리)
이둘을 더한 것이 홀수인지 짝수인지가 여기서 중요한 문제이다.
숫자를 바르게 바꾸면 홀수나 짝수가 항상 유지가 된다.
숫자를 바꿨는데 홀수에서 짝수로 변하거나 짝수에서 홀수로 변하면 못 푼다는 것이다.
3. Cut Off
확실하게 답이 없는 노드는 Cutting한다. 이를 Cut off라고한다.
반응형
'학부 내용 정리 > [ 2-2 ] 알고리즘' 카테고리의 다른 글
| [ 알고리즘 ] Back tracking : N-Queen (0) | 2022.12.05 |
|---|---|
| [ 알고리즘 ] SCC (Strongly Connected Compnent) (0) | 2022.12.05 |
| [ 알고리즘 ] Topological Sort (0) | 2022.12.05 |
| [ 알고리즘 ] Cut Vertex, BBC (0) | 2022.12.04 |
| [ 알고리즘 ] Graph Traversal : Recursive DFS (0) | 2022.12.04 |