[알고리즘] BFS? DFS?

BFS

너비 우선 순회 

Queue로 구현 (큐를 이용하기 때문에 FIFO)

 

장점) 최적해를 찾을 것을 보장한다. 

예를 들어서 지구 상에 존재하는 모든 친구 관계를 그래프로 표현 후, 소깡이와 후리 사이의 관계 경로를 찾는 경우,

BFS - 소깡이와 가까운 관계부터 살핀다.

DFS - 일단, 지구상의 모든 관계를 살핀다.

 

어떤 로직으로 구현되는가?

- 시작 노드를 큐에 삽입하고 방문처리를 한다.

- 큐에서 노드를 꺼낸 후, 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣는다. 그리고 방문 처리를 한다. (방문하면 현재 위치를 pop하고 방문 처리 -> 방문'할' 곳은 큐에 넣는다.)

 

사용 예시

너비 우선 탐색 알고리즘은 많은 문제를 푸는 데 사용된다. 예를 들어,

• 소스 노드(처음 노드)와 다른 노드들 간의 최단거리를 계산할 때(단, unweighted 그래프에서만)
• unweighted 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree)를 계산할 때

와 같은 경우가 있다. 

 

DFS

깊이 우선 순회

Stack과 재귀함수로 구현

 

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 

BFS보다 조금 더 간단하게 구현할 수 있다.

검색 속도 자체는 BFS에 비해서 느리다.

 

장점)

- 현재 경로의 노드들만 기억하면 되므로 저장 공간을 상대적으로 적게 사용한다.

- 목표 노드가 깊은 곳에 있을 경우, 해를 빨리 구할 수 있다.

 

단점)

- 해가 없는 경로를 깊게 탐색할 경우 오래 걸린다. 

- 최적해가 아닐 가능성이 있다. 

 

 

공통점

두 가지 모두 그래프를 탐색하는 방법이다.

 

그래프?

노드와 간선으로 이루어진 자료구조,

하나의 정점에서 시작해서 모든 정점을 한번씩 방문하는 것을 탐색이라고 한다.

 

주의할 점은

그래프를 탐색할 때 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 

그렇지 않으면 무한 루프에 빠질 위험이 있다. 

 

 

---

아래와 같은 그래프가 있을 때, 이 그래프를 BFS 방식과 DFS 방식으로 방문 탐색을 해보자.

 

위의 그래프를 코드로 표현하면, 2차 배열로 나타낼 수 있다.

위에서부터 노드를 넣는데, 하나의 노드를 넣으면 이와 인접한 노드들도 함께 넣는 것이다.

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)

그래서 위와 같이 Bool형의 배열을 만들어준다.

 

이제 DFS, BFS을 구현해보자.

DFS

DFS는 Stack과 재귀함수로 구현하면 된다.

func dfs(v: Int) {
    visited[v] = true // 방문 처리
    
    for i in graph[v].sorted() { // 방문
        if !visited[i] { // 방문하지 않은 노드가 있다면,
            dfs(v: i) // 방문
        }
    }
}

 

 

BFS

BFS는 인접 노드들을 방문하는 것이므로 queue를 이용해서 구현할 수 있다.

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