[Algorithm] DFS / BFS 탐색 알고리즘

 

  DFS / BFS  

	DFS	BFS
탐색 방법	깊이 우선 탐색 (시작 노드 선택은 자유롭지만, 관행적으로 번호가 낮은 순서부터 처리한다.)	너비 우선 탐색 (가까운 것 먼저)
자료구조 / 구현 방법	스택 자료구조 개념 재귀함수를 이용해 구현하면 간결	큐 자료구조 개념 큐를 이용해 구현
시간복잡도	O(N)	O(N)  -실제 수행 시간이 DFS보다 좋다.

 

---

  DFS (Depth-First Search)  

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리한다. 
2. 최상단 노드의 인접 노드를 확인한다. 
    a. 인접노드 중 최상단 노드에 방문하지 않은 노드가 있다면 스택에 삽입 후 방문처리한다.
    b. 방문하지 않은 노드가 없다면, 최상단 노드를 스택에서 꺼낸다. 
3. 모든 노드를 방문할 때 까지 2번 과정을 반복한다.

---

  BFS (Breadth-First Search)  

1. 탐색 시작 노드를 큐에 삽입 후 방문처리한다. 
2. 큐에서 노드를 꺼낸다.
    a. 해당 노드의 인접 노드 중 방문하지 않은 노드가 있다면 큐에 삽입하고, 방문처리한다.
3. 모든 탐색이 끝날 때 까지 2번 과정을 반복한다. 

---

  Coding  

- 왼쪽 나와있는 그래프를 2차원 배열로 표현 다음과 같다.

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

---

1.  DFS  (재귀함수)

// 그래프 정의
let graph: [[Int]] = [[], [2, 5], [1, 3, 4],
                      [2, 4], [2, 3] , [1, 6, 7], [5], [5]]
// 방문여부 확인
var visited = [Bool](repeating: false, count: graph.count) 

// 재귀함수로 구현한 dfs
func dfs(v: Int){
    visited[v] = true // 방문처리
    print(v)
    for i in graph[v].sorted(){
        if !visited[i]{ // 방문하지 않은 노드가 있다면
            dfs(v: i) // 방문
        }
    }
}


dfs(v: 1) // 시작노드 = 1
// 결과 : 1 2 3 4 5 6 7

---

2. BFS (Queue)

func bfs(v:Int){
    var queue:[Int] = [v]
    visited[v] = true
    
    // 큐가 빌 때까지 반복
    while queue.count != 0{ 
    
	// 제일 앞 원소를 꺼낸다
        let v = queue.removeFirst() 
        print(v)
        
        // 인접노드 중 방문하지 않은 원소를 큐에 삽입
        for i in graph[v].sorted(){
            if !visited[i]{
                queue.append(i)
                visited[i] = true // 방문처리
            }
        }
    }
}

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

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

bfs(v: 1)
// 결과: 1 2 5 3 4 6 7

---

 KeyPoint 

📍실제 수행시간을 비교했을 때 BFS가 더 유리하다.

---

  관련 문제  

[백준] 1260 DFS와 BFS

[백준] 2606 바이러스