등고선 알고리즘
- 프로그래밍/자료구조&알고리즘
- 2011. 5. 22. 22:26
등고선 알고리즘이란?
길찾기 알고리즘의 한 종류로 도착점에 0이라는 숫자를 넣고 주변을 검사하여 벽이 아닌 인접한 블록에 -1로 쓴다. 다시 -1 주변을 검사하여 벽이 아닌 인접한 블록에 2를 쓰고,이런 식으로 출발점까지 가장 적은 수가 나오는 경로를 찾아가는 알고리즘이다. 이러한 방법이 마치 등고선을 그리는 방법과 비슷하여 등고선법이라고 한다.
구현방법
1. 각 셀을 -1로 초기화 한다.
-1 | -1 | -1 | ||
-1 | -1 | -1 | ||
-1 | -1 | -1 | -1 | |
-1 | -1 | -1 | ||
-1 | -1 | -1 | -1 |
2. 도착점을 0으로 설정한다.
-1 | -1 | -1 | ||
-1 | -1 | -1 | ||
-1 | -1 | -1 | -1 | |
-1 | -1 | -1 | ||
-1 | -1 | -1 | 0 |
3. 도착점부터 각 셀에 순서대로 번호를 매긴다.
-1 | -1 | 4 | ||
-1 | -1 | 3 | ||
-1 | 4 | 3 | 2 | |
-1 | -1 | 1 | ||
-1 | -1 | -1 | 0 |
4. 출발점을 찾을 때까지 반복한다.
12 | 6 | 4 | ||
11 | 5 | 3 | ||
10 | 4 | 3 | 2 | |
9 | 5 | 1 | ||
8 | 7 | 6 | 0 |
5. 출발점과 도착점의 최단거리를 찾아 그린다. (작은수를 찾아가면 된다.)
12 | 6 | 4 | ||
11 | 5 | 3 | ||
10 | 4 | 3 | 2 | |
9 | 5 | 1 | ||
8 | 7 | 6 | G |
소스코드
// 등고선알고리즘 #include <iostream> #include <conio.h> #define X 19 #define Y 19 #define START 98 #define END 0 int x=0,y=0; void main() { char ch; int map[X][Y] ={ // 미로의모양 {99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99 }, {99,START,99,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,99,-1,-1,-1,99 }, {99,-1,99,-1,99,99,99,-1,99,99,99,99,99,-1,99,-1,99,-1,99 }, {99,-1,99,-1,99,-1,-1,-1,99,-1,-1,-1,-1,-1,99,-1,99,-1,99 }, {99,-1,99,-1,99,99,99,-1,99,99,99,99,99,99,99,-1,99,-1,99 }, {99,-1,99,-1,-1,-1,99,-1,-1,-1,-1,-1,99,-1,-1,-1,-1,-1,99 }, {99,-1,99,99,99,-1,99,-1,99,99,99,-1,99,-1,99,-1,99,-1,99 }, {99,-1,-1,-1,-1,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99 }, {99,99,99,99,99,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99 }, {99,-1,-1,-1,-1,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99 }, {99,-1,99,99,99,99,99,-1,99,-1,99,-1,99,-1,99,-1,99,-1,99 }, {99,-1,-1,-1,-1,-1,-1,-1,99,-1,-1,-1,99,-1,99,99,99,-1,99 }, {99,-1,99,99,99,99,99,-1,99,-1,99,99,99,-1,99,-1,99,-1,99 }, {99,-1,99,-1,-1,-1,-1,-1,99,-1,-1,-1,99,-1,99,-1,99,-1,99 }, {99,-1,99,-1,99,99,99,99,99,99,99,99,99,-1,99,-1,99,-1,99 }, {99,-1,99,-1,99,-1,-1,-1,-1,-1,-1,-1,-1,-1,99,-1,-1,-1,99 }, {99,-1,99,-1,99,-1,99,99,99,99,99,99,99,99,99,99,99,-1,99 }, {99,-1,99,-1,-1,-1,99,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,END,99 }, {99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99 } }; for(int step=0; step<100; step++) { for(int i=0; i<X; i++) { for(int j=0; j<Y; j++) { if( map[i][j] == step) { if(map[i+1][j]==-1) map[i+1][j]= step+1; if(map[i-1][j]==-1) map[i-1][j]= step+1; if(map[i][j+1]==-1) map[i][j+1]= step+1; if(map[i][j-1]==-1) map[i][j-1]= step+1; } } } }
// 현재위치저장 for(int i=0; i<X; i++) { for(int j=0; j<Y; j++) { if(map[i][j]==START) { x=i; y=j; } } } // 최단거리 while (map[x][y]!=END) { if(map[x+1][y] < map[x][y]) x=x+1; else if(map[x-1][y] < map[x][y]) x=x-1; else if(map[x][y+1] < map[x][y]) y=y+1; else y=y-1; system("cls"); for(int i=0; i<X; i++) { for(int j=0; j<Y; j++) { if(i == x && j == y) printf("■"); else if(map[i][j] == 99) printf("□"); else printf(" "); } printf("\n"); } _sleep(200); } scanf("%c",&ch); } |
