<전체 코드를 파일로 올렸습니다>
깊이우선탐색코드.txtC언으로 하는 자료구조를 하다보면 리커시브가 상당히 많이 나온다. 그런데 기본적으로 아주쉽고, 직관적으로 알 수 있는 리커시브가 아니라,
상당히 난해하고 머리로 쉽게 이해하지 못하는 리커시브가 많이 등장한다. 그래서 이번에 상당히 복잡한 리커시브를 확실히 이해하고자 한다.
쓰인 코드는 깊이 우선 탐색으로, 갈 수 있는 경로를 구하는 코드이다. 어쨋든 사용되는 리커시브를 통해 리커시브를 완벽히 이해하자.
노드의 모양은 이러하다.
만약 내가 0번 노드에서 시작을 한다면 0에서 갈 수 있는 노드는 3번과 4번노드가 있다. 둘중에 숫자가 작은 노드를 선택한다.
그러면 3이 선택될 것이고 3번 노드는 또 다시 갈 수 있는 길을 탐색 할 것이다. 이때 0번은 지나온 길이므로 갈 수 없음을 표시하고,
나머지 노드중 가장 작은 녀석으로 이동한다. 즉 순서를 나타내면 0 -> 3 ->2 ->4 이다. 여기까지는 직관적으로 쉽게 이해 가능하다.
그런데 이제부터 리커시브 되는게 이해가 잘 안되었다. 핵심 코드는 아래와 같다.
void dfs_mat_path(GraphType* g, int i, int goal){
int j, k;
visited[i] = 1; //방문한 노드를 1로 표시하여 다시 방문하지 않게 함.
if (parent[count] != i)//방문한 노드를 저장.
parent[count] = i;
count++;
//만약 i가 목표지점에 도달하면 모두 방문했다고 표시하여 다른 노드를 가는 경우를 차단합니다.
if (i == goal)
for (k = 0; k < g->n; k++)
visited[k] = 1;
for (j = 0; j < g->n/*9개*/; j++){
//adj_mat[i][j]==1는 인접을 나타냄, visited[j]==0는 방문한적이 없음을 나타냄
if (g->adj_mat[i][j] == 1 && visited[j] == 0){
printf("%d -> %d, ", i, j); //경로를 출력
dfs_mat_path(g, j, goal); //다음 노드를 재귀 탐색 합니다.
}
}
}
for문을 유심히 보면된다. 0부터 노드의 개수까지 for문을 돌아 갈수 있는 경로를 탐색한다.
<<손으로 적은 리커시브 내용-위에 올린 그림을 참고하여 경로를 손으로 써봄>>
이런식으로 계속해서 리커시브로 자신을 불러와서 0부터 노드 개수까지 for문을 돌면서 갈 수 있는 경로를 찾는 것이다.
0번노드부터 8번노드까지 가는 경로를 깊이우선탐색으로 진행하다보면 6번노드에서 문제가 생긴다.
6번노드를 선택 후 for문을 돌면 0번부터 순서대로 for문을 돌기때문에 5번노드를 8번 노드보다 먼저 방문하게 된다.
그럼 어떻게 될까? 이때 리커시브의 장점인 백트래킹이 발생하게 된다. 백트래킹은 지나왔던 경로로 다시 되돌아가는 것을 말한다.
<<손으로 적은 백트래킹 내용은 아래와 같다.>>
결론: 이렇게 그림을 그려서 코드를 이해하니 훨씬 쉬웠다. 물론 비쥬얼스튜디오의 디버깅 기능을 이용하여 대략적인 내용을 파악하였기에
손쉽게 그림을 그릴 수 있었다. 앞으로도 어려운 코드가 나오면 디버깅과 손을 이용하여 최대한 이해 할 생각이다.
왜 깊이우선탐색이나 이진탐색트리 등에 리커시브를 사용하는지 확실히 알 수 있었다.
바로 너무나도 매력적인 백트래킹 기능때문이다.. 자신이 알아서 막히면 뒤로 간다니 진짜 프로그래밍이라는건 대박인것 같다. ㅎㅎ
