DFS 경로탐색

DFS를 이용하여 경로탐색 하는 방법

K F C M 을 이용하여 경로 탐색한다.
K에서 M까지 가는 경로의 수를 구한다.

1. 사이클이 발생할 수 있기 때문에 체크한다.
2. 맨 끝 지점을 확인한다.

변수가 M 3번에 해당하는 지점에 있다면 모든 경로를 거쳐 도달했다는 것임
그러므로 변수가 3번 지점에 있는 경우를 찾으면 됨

총 네가지 경로가 나온다.

**char name[5] = "KFCM";
int map[4][4] = {
0,1,1,0,
0,0,1,1,
0,1,0,1,
0,0,0,0
};

void dfs(int now)
{
if (now == 3) cnt++;
//now가 3인 경우는 끝에 도달한 것임
for (int x = 0; x < 4; x++)
{
if (map[now][x] == 1 && used[x] == 0)
{
used[x] = 1; //한번 방문한 곳은 1로 처리한다.
dfs(x);
used[x] = 0; //방문 다하면 리턴시키고 0으로 초기화함
// 예를들어 1 1 1 1로 다 방문 하면 1 1 1 0 으로 하고 그 전의 값으로 이동한다.
// 전의 값으로 이동하여 새로운 경로 (m으로 가는)를 탐색한다.
}
}
}
int main()
{

used[0] = 1;
dfs(0);
cout << cnt << "가지 방법 있다.";
return 0;

}