[알고리즘] DFS

오늘은 코딩테스트의 꽃이 DFS에 대해서 정리해보려한다. BFS는 내일 정리하는걸 목표로 한다.
DFS는 Depth First Search의 약자로 깊이 우선 탐색,
BFS는 Breadth First Search의 약자로 넓이 우선 탐색을 이야기한다.

1. DFS

1. 순환 알고리즘 형태이기에 스택과 재귀함수로 푸는것이 좋다.
2. 그래프 탐색시 어떤 노드에 방문했었는지 여부를 반드시 검사해야 한다. 검사하지 않을 경우에 무한루프에 빠질 수 있다.
3. BFS 보다 간단하지만 속도는 느리다.
4. 백트래킹 : 탐색 마친 후 이전의 정점으로 되돌아온다.
   

1.1 인접행렬 DFS

: for loop을 V번 탐색하기에 O(V), V개의 정점을 모두 방문한다.
시간복잡도 = V * O(V) = O(V^2)

void dfs(int x){
  check[x] = true;
  
  for(int i = 1; i <= V ; i++){
  	if(graph[x][i] == 1 && !check[i]){
      	dfs(i);
       }
  }
}

1.2 인접리스트 DFS

: DFS 하나당 각 정점에 연결되어 있는 간선의 갯수 만큼 탐색하기에 수행시간이 제각각.
총 정점인 V번 탐색하고 DFS의 정점마다 인접한 노드 E번을 검사하기에 O(V+E)의 시간 소요

void dfs(List[] list, boolean check, int x) {

  check[x] = true;
  
  for(int i = 0; i < list[x].size(); i++){
  	int next = (int)list[x].get(i);
      if(!check[next])
      	dfs(next);
  }
}