간단한 미로찾기 알고리즘(깊이탐색알고리즘, DFS)

깊이우선탐색(DFS) 알고리즘이란?

현재 위치와 붙어있는 간선들을 하나씩 검사하다가 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라 간다. 이걸 반복하면서 더 이상 갈 곳이 없다면 마지막에 따라왔던 간선을 따라 뒤로 돌아가면서 탐색이 이루어 진다.

쉽게 말해서 1~10번 우물을 파야한다면 1번부터 끝까지 다 파보고 2번으로 넘어가는 방법이라고 볼 수 있다.

DFS를 이용해서 간단하게 미로찾기를 구현해보았다.

#include<stdio.h>

int map[11][11]={ 1,1,1,1,1,1,1,1,1,1,1,

1,0,0,0,0,0,0,0,0,0,1,

1,0,0,1,1,1,1,1,1,0,1,

  1,1,0,1,1,1,1,1,1,0,1,

1,1,0,1,1,1,1,1,1,0,1,

1,1,0,0,1,1,0,0,0,0,1,

1,1,1,0,0,1,0,1,0,0,1,

1,1,1,1,0,1,0,1,0,0,1,

1,1,1,1,0,0,0,1,1,0,1,

1,1,1,1,1,1,1,1,1,0,1,

1,1,1,1,1,1,1,1,1,1,1};

int sw=0;

void dfs(int i,int j){

if(map[i][j]==0){

if(i==9 && j==9){ //출구

sw=1;

}else if(map[i][j] == 0){ //출구가 아닌데 그 자리가 벽이 아니라면

map[i][j]=1; //벽으로 만들고

if(sw==0) dfs(i+1,j); //하

if(sw==0) dfs(i,j+1); //우

if(sw==0) dfs(i,j-1); //좌

if(sw==0) dfs(i-1,j); //상

map[i][j]=0; //벽 풀고 다시 길로 만들어주고

}}

if(sw==1){

printf("(%d,%d)",i,j);

}

}

int main(void){

dfs(1,1);

if(sw==0)

printf("출구없음\n");

}