DFS/BFS

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

DFS란?

깊이 우선 탐색이라고도 부르며, 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간 복잡도를 가진다.

 

DFS를 스택 자료구조를 이용하여 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

※ "방문 처리"는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미

최상단 노드 - 파란색, 방문 처리 노드 - 회색

DFS를 이용하여 탐색하는 과정

1. 시작 노드인 1을 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드인 1에 방문하지 않은 인접 노드 2,3,8중 가장 작은 노드인 2를 스택에 넣고 방문처리

3. 스택의 최상단 노드인 2에 방문하지 않은 인접노드 7을 스택에 넣고 방문처리

4. 스택의 최상단 노드인 7에 방문하지 않은 인접노드 6,8중 가장 작은 노드인 6을 스택에 넣고 방문 처리

5. 스택의 최상단 노드인 6에 방문하지 않은 인접 노드가 없으므로 6번노드를 스택에서 꺼냄

6. 스택의 최상단 노드인 7에 방문하지 않은 인접노드 8을 스택에 넣고 방문 처리

7. 스택의 최상단 노드인 8에 방문하지 않은 인접노드가 없으므로 8을 스택에서 꺼냄

8. 스택의 최상단 노드인 7에 방문하지 않은 인접노드가 없으므로 7을 스택에서 꺼냄

9. 스택의 최상단 노드인 2에 방문하지 않은 인접노드가 없으므로 2를 스택에서 꺼냄

10. 스택의 최상단 노드인 1에 방문하지 않은 인접노드 3을 스택에 넣고 방문 처리

11. 스택의 최상단 노드인 3에 방문하지 않은 인접노드 4,5중 가장 작은 노드인 4를 스택에 넣고 방문처리

12. 스택의 최상단 노드인 4에 방문하지 않은 인접노드 5를 스택에 넣고 방문 처리

13. 남아있는 노드에 방문하지 않은 인접노드가 없으므로 모든 노드를 차례대로 스택에서 꺼냄

 

위 과정을 거치면 노드의 탐색 순서는 

1 → 2 → 7 → 6 → 8 → 3 → 4 → 5 

 

소스코드

let graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

var visited = Array(repeating: false, count: graph.count)

func dfs(node: Int) {
    
    // 현재 노드 방문 처리
    visited[node] = true
    print("node = \(node)")

    for i in graph[node] {
        if visited[i] == false {
            dfs(node: i)
        }
    }
}

dfs(node: 1)

// 1 2 7 6 8 3 4 5

 

BFS란?

너비 우선 탐색이라고도 부르며 가까운 노드부터 탐색하는 알고리즘이다.

DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하지만 BFS는 그 반대로 동작한다.

BFS는 선입선출 방식인 큐 자료구조를 이용한다.

탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간 복잡도를 가진다.

 

BFS를 큐 자료구조를 이용하여 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

최상단 노드 - 파란색, 방문 처리 노드 - 회색

BFS를 이용하여 탐색하는 과정

1. 시작 노드인 1을 큐에 삽입하고 방문처리

2. 큐에서 노드 1을 꺼내고 방문하지 않은 인접노드 2,3,8을 모두 큐에 넣고 방문처리

3. 큐에서 노드 2를 꺼내고 방문하지 않은 인접노드 7을 큐에 삽입하고 방문처리

4. 큐에서 노드 3을 꺼내고 방문하지 않은 인접노드 4,5를 모두 큐에 넣고 방문처리

5. 큐에서 노드 8을 꺼내고 방문하지 않은 인접노드가 없으므로 다음단계 진행

6. 큐에서 노드 7을 꺼내고 방문하지 않은 인접노드 6을 큐에 넣고 방문처리

7. 남아있는 노드에 방문하지 않은 인접노드가 없으므로 모든 노드를 큐에서 차례대로 꺼냄

 

위 과정을 거치면 노드의 탐색 순서는

1 → 2 → 3 → 8 → 7 → 4 → 5 → 6

 

소스코드

let graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

var visited = Array(repeating: false, count: graph.count)
var queue = [Int]()

func bfs(node: Int) {

    // 현재노드 방문처리
    visited[node] = true

    // 현재노드 큐에 추가
    queue.append(node)

    // 큐가 빌때까지 반복
    while !queue.isEmpty {
        
        // 먼저 들어온 노드 꺼냄
        let front = queue.removeFirst()
        print("노드 = ",front)
        
        // 꺼낸 노드를 기준으로 인접 노드 방문처리 및 큐에 삽입
        for i in graph[front] {
            if visited[i] == false {
                queue.append(i)
                visited[i] = true
            }
        }
    }
}

bfs(node: 1)

// 1 2 3 8 7 4 5 6