(출처 :: https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%82%AC%EC%9D%98_%EC%97%AC%ED%96%89)
8*8 체스판 위에 특정 좌표로 시작하여 나이트가 모든 체스판을 투어 할 수 있는지 알아보는 알고리즘이다.
가장 Naive한 방법으로는 단순 백트래킹을 이용하는 방법이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <iostream> #include <cstdio> #include <memory.h> #define N 8 using namespace std; int dy[N] = { -2,-1,1,2,2,1,-1,-2 }; int dx[N] = { 1,2,2,1,-1,-2,-2,-1 }; bool chkSafe(int y, int x, int arr[N][N]) { if ((0 <= x && x < N) && (0 <= y && y < N) && arr[y][x] == -1) return true; return false; } bool knightTour(int index, int y, int x, int arr[N][N]) { if (index == N * N) { arr[y][x] = index - 1; return true; } for (int i = 0; i < N; i++) { int ny = y + dy[i]; int nx = x + dx[i]; int val = 0; if (chkSafe(ny, nx, arr)) { arr[y][x] = index - 1; if (knightTour(index + 1, ny, nx, arr)) return true; else arr[y][x] = -1; } } return false; } int main() { int x, y; cin >> x >> y; int arr[N][N]; memset(arr, -1, sizeof(arr)); arr[y][x] = 0; knightTour(1, y, x, arr); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) cout << arr[i][j] << " "; cout << endl; } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
현재 위치에서 다음 위치로 갈 수 있는지 파악해주고, 그렇지 않다면 되돌아와서 다른 방향으로 다시 가보는 방식을 이용한다.
완전 탐색류인 백트래킹의 특성 상 시간이 오래 걸릴 수 있다.
(특히 테스트케이스가 많아진다면 더 그런 현상이 잦아질 것이다.)
이를 더 최적화 시킬 방법이 없을까 해서 나타난 알고리즘이 Warnsdorff's Rule이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 | #include <iostream> #include <cstdio> #include <memory.h> #define N 8 using namespace std; int dy[N] = { -2,-1,1,2,2,1,-1,-2 }; int dx[N] = { 1,2,2,1,-1,-2,-2,-1 }; bool chkSafe(int y, int x, int arr[N][N]) { if ((0 <= x && x < N) && (0 <= y && y < N) && arr[y][x] == -1) return true; return false; } bool warnsdorff(int index, int y, int x, int arr[N][N]) { if (index == N * N) { arr[y][x] = index - 1; return true; } int minVal = N; int minIdx = -1; for (int i = 0; i < N; i++) { int ny = y + dy[i]; int nx = x + dx[i]; int val = 0; if (chkSafe(ny, nx, arr)) { for (int j = 0; j < N; j++) { int ty = ny + dy[j]; int tx = nx + dx[j]; if (chkSafe(ty, tx, arr)) val++; } if (minVal > val) { minVal = val; minIdx = i; } } } int ny = y + dy[minIdx]; int nx = x + dx[minIdx]; int val = 0; if (chkSafe(ny, nx, arr)) { arr[y][x] = index - 1; if (warnsdorff(index + 1, ny, nx, arr)) return true; else arr[y][x] = -1; } return false; } int main() { int x, y; cin >> x >> y; int arr[N][N]; memset(arr, -1, sizeof(arr)); arr[y][x] = 0; warnsdorff(1, y, x, arr); for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) cout << arr[i][j] << " "; cout << endl; } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
이 알고리즘은 기본 백트래킹에서 휴리스틱 방식으로 조금 더 추가되었는데
나이트가 이동 할 수 있는 지점 중에서 degree가 가장 작은 지점으로 이동해야 한다.
이때 degree의 의미는 해당 지점에서 다른 지점으로 이동 할 수 있는 지점의 개수를 의미한다.
|
|
|
|
|
|
|
|
|
O |
O |
|
|
|
|
|
X |
|
|
O |
|
|
|
|
|
|
현재지점 |
|
|
|
|
|
|
|
|
|
|
|
|
|
O |
|
|
|
X |
|
|
|
|
O |
|
X |
|
|
|
|
|
|
|
|
|
|
|
|
위와 같이 나이트가 있다고 가정해보자.
그렇다면 현재 지점에서의 degree는 5라고 할 수 있다.(X가 이미 나이트가 방문 한 곳, O가 나이트가 방문 할 수 있는 곳)
따라서 Warnsdorff's Rule을 이용하여 degree가 더 적은 곳, 즉 현재 지점에서 방문 할 곳이 별로 없는 곳을 기준으로 계속해서 탐색을 하면 좀 더 효율적인 나이트 투어를 할 수 있게 된다.
코드의 핵심은 다음과 같다.
1. 현재 지점에서 8개의 다음 지점을 본다.
2. 다음 지점의 degree를 관찰한다.
3. 8개의 다음 지점에서 degree가 가장 작은 지점을 현재 지점에서 다음 지점으로 갈 곳으로 선택한다.
'Applied > 알고리즘' 카테고리의 다른 글
| 선형 합동 생성기(Linear Congruential Generator, LCG) (0) | 2018.01.31 |
|---|---|
| 하노이 탑 K번째 찾기 (2) | 2018.01.26 |
| MCMF(Minimum Cost Maximum Flow) 알고리즘 (0) | 2017.12.05 |
| SPFA (Shortest Path Faster Algorithm) (4) | 2017.12.04 |
| 디닉 알고리즘(Dinic's Algorithm) (0) | 2017.12.02 |