-
등고선 알고리즘@ 16. 1 ~ 17. 1/알고리고리즘 2013. 9. 19. 23:38
등고선 알고리즘이란?
길찾기 알고리즘의 한 종류로 도착점에 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);
}
출처 : http://blog.naver.com/ohrak22
'@ 16. 1 ~ 17. 1 > 알고리고리즘' 카테고리의 다른 글
퀵 정렬 (0) 2015.10.02 힙 정렬 (0) 2015.10.02 거품 정렬 (0) 2015.09.30