등고선법알고리즘을이용한미로의최적해찾기

소개글

등고선법알고리즘을이용한미로의최적해찾기에 대한 보고서 자료입니다.

목차

1. 숙제 설명

2. 프로그램 설명

3. 소스파일

본문내용

ol,wheretogo[4]={0,0,0,0};
if(row==start.row&&col==start.col)//현재 지점(row,col)이 시작점이라면 길이존재하는 것이므로
find=1;//find를 1로 변경
if(tmpmiro[row-1][col-1].distance==0)//현재 지점(row,col)의 distance변수에 전달받은 distance를 저장
tmpmiro[row-1][col-1].distance=distance;
else
if(tmpmiro[row-1][col-1].distance>distance)//현재 지점(row,col)에 이미 distance가 저장되어있는데
tmpmiro[row-1][col-1].distance=distance;//그 값이 인수로 받은 값보다 크다면 작은 값으로 갱신
while(tmpdir<4){
tmprow=row+direction[tmpdir].row;//현재 지점(row,col)에서 동서남북쪽에 있는
tmpcol=col+direction[tmpdir].col;//각각의 블록에 대해서
if(tmprow<51&&tmprow>0&&tmpcol<51&&tmpcol>0){//벽이라면 그냥 무시하고
if(tmpmiro[tmprow-1][tmpcol-1].path==0){//길이라면 그곳에 각각 현재의 distance에
if(tmpmiro[tmprow-1][tmpcol-1].distance>distance+1){//1을 더한 값을 distance로 하여
checkdistance(tmprow,tmpcol,distance+1);//저장
wheretogo[tmpdir]=1;
}
else if(tmpmiro[tmprow-1][tmpcol-1].distance==0){
checkdistance(tmprow,tmpcol,distance+1);
wheretogo[tmpdir]=1;
}}}
tmpdir++;
}
for(i=0;i<4;i++)//위의 과정에서 동서남북 중에
if(wheretogo[i]==1){//길이라고 밝혀진 방향에 대해서
tmprow=row+direction[i].row;//각각 다시 checkaround()함수를 호출하여
tmpcol=col+direction[i].col;//미로를 형성하는 모든 블록에 대해서 조사함
checkaround(tmprow,tmpcol,distance+1);
}
}
/*인수를 전달받은 블록에 distance를 기록하는 함수*/
void checkdistance(int row, int col, int distance){//인수로 주어진 row,col위치에
if(tmpmiro[row-1][col-1].distance==0)//distance가 0이면 인수로 주어진 distance를 저장하고
tmpmiro[row-1][col-1].distance=distance;//distance가 있으면 인수로 주어진 distance와 비교하여
else if(tmpmiro[row-1][col-1].distance>distance)//작은것을 저장한다
tmpmiro[row-1][col-1].distance=distance;
}
/*미로의 길을 찾는 함수*/
void search(int row, int col){
int i,cnt,nextgo=0,small=3000,nextrow,nextcol,dir,wch[4]={0,0,0,0};
block now;
if(row==end.row&&col==end.col){//인수로 주어진 row, col의 블록이 끝점이면
now.row=row;//스택에 저장하고 끝낸다
now.col=col;
push(&top, now);
}
else{//끝점이 아니라면
checkmiro[row-1][col-1]=1;//임시미로배열에 지나감을 표시하고
dir=0;
cnt=0;
while(dir<4){//현지점에서 동서남북방향을 확인하여
nextrow=row+direction[dir].row;//길이면서 전에 지나가지 않은 곳을 체크한다
nextcol=col+direction[dir].col;
if(nextrow<51&&nextrow>0&&nextcol<51&&nextcol>0){
if(miro[nextrow-1][nextcol-1]==0&&checkmiro[nextrow-1][nextcol-1]==0){
cnt++;
wch[dir]=tmpmiro[nextrow-1][nextcol-1].distance;
}}
dir++;
}
if(cnt==0&&top>-1){//동서남북 모두 길이 아니거나 전에 지나가서 새로운 길이 없으면
now=pop(&top);//스택에서 pop을 하여 그곳에서 다시 search한다
search(now.row,now.col);
}
else{//동서남북중 새로운 길이 한곳이라도 있다면
for(i=0;i<4;i++){
if(wch[i]!=0)
if(small>wch[i]){
small=wch[i];
nextgo=i;
}}
now.row=row;
now.col=col;//현지점을 스택에 push하고
nextrow=row+direction[nextgo].row;//그 새로운 길에 대해서 search한다
nextcol=col+direction[nextgo].col;
push(&top,now);
search(nextrow,nextcol);
}}
}
/*스택에 push하는 함수 */
void push(int *top, block now){
if(++(*top)==2500)//스택에 이미 꽉차 있다면 에러를 출력한다
printf("\nERROR!!! STACK OVERFLOW!!!\n");//top을 1증가시키고
stack[*top].col=now.col;//top부분에 삽입한다
stack[*top].row=now.row;
}
/*스택에서 pop하는 함수 */
block pop(int *top){
block temp;
temp=stack[*top];//스택에서 top부분을 빼서
if(--(*top)<-1)//(top을 1감소시킨다
printf("\nCAUTION!!! STACK EMPTY!!!\n");//이때 크기가 -1보다 작으면 에러를 출력한다)
return temp;//리턴한다
}

키워드

등고선법,   미로,   최적해,   찾기,   알고리즘