[C#] 그래프 탐색 알고리즘 DFS (Depth First Search) : 깊이우선탐색

인프런 [C#, Unity] 관련 강의에서 미로찾기 게임을 구현하기 위해 DFS, BFS알고리즘을 배웠다.

정리해놓지 않으면 금방 까먹을 거 같아서 내가 이해한 식으로 정리하고 코드 기록하기!

DFS는 깊이우선탐색 알고리즘으로 그래프의 모든 정점들을 한번씩 방문하면서 탐색을 하게 된다.

DFS는 한 정점의 간선으로 이동하게 되면 목적지까지 탐색을 마친 후, 다시 돌아가 다음 정점을 탐색하는 특징이 있다.

재귀함수, Stack 을 이용해서 간단하게 구현할 수 있다.

1. Graph : 그래프는 다른 선형구조처럼 클래스로 구현되어있지 않아 사용자가 편한 대로 구현하면 된다.

List <int>[] graph = new List<int>[]{
  new List<int>(){1, 3},
  new List<int>(){0, 2, 3},
  new List<int>(){1},
  new List<int>(){0, 1, 4},
  new List<int>(){3,5},
  new List<int>(){4},
}

2. 탐색여부를 체크할 boolean array : 해당 array가 모두 true 값이 될 때, 종료조건이 된다.

bool[] found = new bool[6]; // graph의 size

3. DFS 함수 (재귀함수)

public void DFS(int start)

public void DFS(int start)
{
  found[start] = true;
  foreach(int next in graph[start]
  {
    if(found[start]) // 이미 탐색한 곳이면 pass
      continue;
    DFS(next);
  }
}

4. 탐색 순서 예상해보기

4-1. start가 0번 노드일 경우, 1번을 먼저 방문한다 found = [T, T, F, F, F, F]; Stack Size = 1 > 2;

4-2. start가 1번 노드일 경우, 0번은 true이므로 패스하고, 2번을 방문한다 found = [T, T, T, F, F, F]; Stack Size = 2 > 3;

4-3. start가 2번 노드일 경우, 1번은 true이므로 패스한다. 해당 함수는 종료된다. Stack Size = 3 > 2;

4-4. 다시 4-2 함수를 이어서 실행해서 start는 1번 노드이고, 3번을 방문한다. found = [T, T, T, T, F, F]; Stack Size = 2 > 3;

4-5. start가 3번 노드일 경우, 0, 1번은 true이므로 패스하고, 4번을 방문한다. found = [T, T, T, T, T, F]; Stack Size = 3 > 4;

4-6. start가 4번 노드일 경우, 3번은 true이므로 패스하고, 5번을 방문한다. found = [T, T, T, T, T, T]; Stack Size = 4 > 5;
=========================found가 모두 완료 되었으므로, 재귀함수는 호출 되지 않으며 그동안 스택에 호출된 함수들이 pop()될 차례;

4-7. start가 5번 노드일 경우, 4번은 true이므로 패스한다. 해당 함수는 종료된다. Stack Size = 5 > 4;

4-8. 다시 4-6 함수를 이어서 실행하고 start는 4번 노드이며 해당 함수는 종료된다. Stack Size = 4 > 3;

4-9. 다시 4-5 함수를 이어서 실행하고 start는 3번 노드이며 해당 함수는 종료된다. Stack Size = 3 > 2;

4-10. 다시 4-2 함수를 이어서 실행하고 start는 1번 노드이며 해당 함수는 종료된다. Stack Size = 2 > 1;

라스트팡. 4-1 함수를 이어서 실행하고 start는 0번 노드이며 해당 함수는 종료된다. Stack Size = 1 > 0;