[Algorithm] - DFS(Depth-First Search)

알고리즘 문제에서 자주 다뤄지는 DFS에 대해 알아보자.

 

DFS란?

 

DFS는 말 그대로 깊이 우선 탐색으로 인접한 노드부터 넓게 탐색하는 BFS와 달리 깊이를 우선으로 탐색하는 방법이다.

하나의 정점에서 시작하여 그 정점의 깊이까지 우선적으로 탐색하는 방법을 말한다.

 

❗️dfs 사용하는 경우: 모든 노드를 방문하고자 하는 경우

 

 

ex) 어떤 지점 a에서 b까지 이동하는 거리를 그래프로 표현한 후 a와 b사이에 존재하는 경로를 찾는 경우

   

   > DFS - 일단 한 경로를 선택하여 끝까지 가보고 막혔다면 다시 이전 분기점으로 돌아와 탐색

   > BFS - 시작점과 가까운 곳부터 '차례대로' 살펴보며 탐색

 

 

DFS 특징

 

 

1️⃣ DFS는 BFS보다 비교적 간단하다.

 

2️⃣ 단순 검색 속도 자체는 BFS에 비해 느리다.

 

3️⃣ 자주 재귀적으로 구현된다.

 

4️⃣ 어떤 노드를 방문했었는지 여부를 반드시 확인해야 한다. (무한루프에 빠질 위험이 있다)

 

 

---

DFS 이해

 

📌 DFS 과정

 

 

 

1. 시작점 1노드 방문

visited[1] = true

 

2. 1노드와 인접한 2노드 방문

visited[1, 2] = true

 

3. 2노드와 인접한 4노드 방문

visited[1, 2, 4] = true

 

4. 4노드와 인접한 5노드 방문

visited[1, 2, 4, 5] = true

 

5. 더이상 방문할 노드 없어서 backtracking

 

6. 이전노드로 돌아가서 시작노드에서부터 다시 이웃노드 방문 (3노드)

 

7.  3노드까지 방문, 모든 노드 방문했으니 탐색 종료

visited[1, 2, 4, 5, 3] = true

 

🔎 DFS 동작과정

1. 시작 노드 선택
2. 현재 노드 방문 및 표시
3. 인접 노드 중 방문하지 않은 노드 선택
4. 선택한 노드로 이동
5. 더 이상 방문할 노드가 없다면 이전 단계로 돌아간다.
6. 모든 노드를 방문할 때까지 반복

 

 

 

📌 DFS 구현

 

DFS를 구현하는 방법 2가지

 

• 재귀
• 스택

 

1️⃣ 재귀

 

import Foundation

var graph: [Int: [Int]] = [
    1: [2, 3, 4],
    2: [1, 4],
    3: [1, 4],
    4: [1, 2, 5],
    5: [4]
]

var visited: [Bool] = Array(repeating: false, count: graph.count + 1)

func dfs(_ v: Int) {
    visited[v] = true // 정점 방문처리
    print(v, terminator: " ") // 방문한 정점 출력
    
    // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    if let neighbors = graph[v] {
        for i in neighbors {
            // 방문하지 않은 노드일 경우 -> dfs 다시 수행
            if !visited[i] {
                dfs(i)
            }
        }
    }
}

// 시작노드를 1로 설정
dfs(1)

 

 

 

 

 

 

2️⃣ 스택

 

import Foundation

var graph: [Int: [Int]] = [
    1: [2, 3, 4],
    2: [1, 4],
    3: [1, 4],
    4: [1, 2, 5],
    5: [4]
]

func dfsStack(_ startNode: Int) {
    var stackDFS: [Int] = [] // 저장할 스택
    var visited: [Bool] = Array(repeating: false, count: graph.count + 1) // 방문 여부 배열 초기화
    stackDFS.append(startNode) // 시작노드 startNode로 설정

    // 숫자가 작은 순서대로 꺼내기 위해 인접노드를 내림차순으로 정렬
    for v in graph.keys {
        graph[v]?.sort(by: >)
    }

    // 스택이 빌 때까지 반복
    while !stackDFS.isEmpty {

        // 스택의 최상위 노드를 꺼냄
        let node = stackDFS.removeLast()

        // node가 방문하지 않았다면
        if !visited[node] {
            // 방문처리
            visited[node] = true
            print(node, terminator: " ")
            if let neighbors = graph[node] {
                stackDFS += neighbors
            }
        }
    }
}

// 시작노드를 1로 설정
dfsStack(1)

 

 

✏️ DFS 시간 복잡도

 

정점의 수: N, 간선의 수: E

 

1️⃣ 인접 리스트: O(N+E) 

 

: 간선의 수에 직접적으로 의존하며, 각 노드의 인접리스트를 순회한다.

 

• 정점 수 N에 대한 순회 O(N)
• 모든 인접 리스트 길이 합이 간선 수 E
• => O(N+E)

 

 

2️⃣ 인접 행렬: O(N^2)

 

: 간선의 유무를 행렬로 표현하며, 노드의 수가 많은 경우 시간복잡도에 걸릴 수 있다.

 

• 모든 정점을 다 찾아봐야 하기 때문에 dfs() 시간 복잡도는 O(N)
• dfs()가 N번 호출되므로 => O(N*N) = O(N^2)