DFS, BFS

📌 깊이 우선 탐색(DFS, Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 지님

• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

구현

fun dfs(index: Int) {
    visited[index] = true
    println(index)

    // 구현
    for (next in graphs[index]) {
        if (!visited[next]) {
            dfs(next)
        }
    }
}

장단점

• 장점
  • 백트래킹 해야하는 노드들만 저장하면 되기 때문에 BFS에 비해 저장공간의 필요성이 적다.
  • 찾아야하는 노드가 깊은 단계에 있을 수록, 그 노드가 좌측에 있을수록 BFS보다 유리하다.
• 단점
  • 답이 아닌 경로가 매우 깊다면, 그 경로에 깊이 빠질 우려가 있다.
  • 최단 경로 길찾기에 적합하지 않다.

📌 너비 우선 탐색(BFS, Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

특징

• BFS 는 재귀적으로 동작하지 않는다.

• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

• BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함

구현

val queue = LinkedList<Int>()
fun bfs(start: Int) {
 	queue.add(start)
   	visited[start] = true

    while (queue.isNotEmpty()) {
    	val head = queue.poll() // 첫 원소 반환 후 remove
    	println(head)

        for (next in graphs[head]) {
            if (!visited[next]) {
                visited[next] = true
                queue.add(next)
            }
        }
    }
}

장단점

• 장점
  • 최초 발견 루트를 최단경로라고 보장할 수 있다.
  • 언제나 같은 거리 결과값을 얻을 수 있다.
  • 노드 수가 적고 깊이가 얕은 해가 존재 할 때 유리하다.
• 단점
  • 재귀호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색 할 노드들을 저장하기 때문에 노드의 수가 많을 수록 필요없는 노드들까지 저장해야 하기 때문에 더 큰 저장공간 필요.
  • 노드의 수가 늘어나면 탐색해야하는 노드가 많아지기 때문에 비효율적

📌 DFS와 BFS 비교

• DFS의 시간복잡도
  인접 리스트로 표현된 그래프 : O(N+E)
  인접 행렬로 표현된 그래프: O(N^2)
  👉 적은 수의 간선을 사용할 때는 인접 리스트가 더 유리하다.

• BFS의 시간복잡도
  인접 리스트로 표현된 그래프 : O(N+E)
  인접 행렬로 표현된 그래프: O(N^2)
  👉 DFS와 마찬가지