[Algorithm] Breadth-First Search(BFS)

오늘의 알고리즘 Topic은 Breadth-first search(너비우선탐색)입니다.

사실 BFS라고 더 많이 불리고 있습니다. BFS하면 짝꿍 DFS도 빠질 수 없습니다.

DFS는 이후 게시글에서 알아보도록하고 오늘은 BFS를 먼저 살펴보겠습니다.

특징

출처: https://en.wikipedia.org/wiki/Breadth-first_search

BFS의 기본 개념은 Tree 구조에서 파생되었고, Tree의 노드를 순회하는 방식 중에 하나입니다.

어떠한 자료구조를 순회할 때는 항상 기준이 중요합니다. BFS의 기준은 바로 현재 노드의 Depth입니다.

 

Tree는 기본적으로 Depth라는 개념이 있습니다.

Root 노드로부터 몇번째 자식노드냐에 따라 Depth가 정해집니다.

위 사진에서 최상단의 붉은 원이 Root노드이며, 11 노드는 Root 노드로부터 3번째 노드이므로 Depth가 3입니다.

Tree 노드들의 최대 Depth 값은 3이므로 Depth가 3인 Tree가 됩니다.

출처: https://en.wikipedia.org/wiki/Tree_(data_structure)

BFS는 현재 노드의 Depth를 기준으로 순회한다고 했습니다.

만약 바로 위의 Tree를 BFS를 통해서 순회한다면 어떤 순서가 될까요?

우선 Depth를 기준으로 데이터를 분류해보겠습니다.

Depth: 0 = [2] 
Depth: 1 = [7, 5] 
Depth: 2 = [2, 10, 6, 9] 
Depth: 3 = [5, 11, 4]

혹시 제가 분류해놓은 데이터 속에서 약간 규칙이 보이시나요?

데이터가 많지 않아 한눈에 알기 쉽지는 않지만, 왼쪽에서 오른쪽으로 방향으로 수를 나열했습니다.

 

물론 Tree를 어떻게 구현하는냐에 따라 다르겠지만, 평범한 Tree의 경우 자식노드가 추가된 순서대로, Binary Tree의 경우 Left->Right 순서대로 등 순회 순서가 있을 때 일정한 경로로 순회가 가능합니다.

또한 이러한 방식으로 순회를 하기위해 Queue가 사용됩니다. 어떻게 사용되는지는 구현 파트에서 알아보도록 하겠습니다.

 

따라서 위 예시의 경우 Depth에 따라

2 -> 7 -> 5 -> 2 -> 10 -> 6 -> 9 -> 5 -> 11 -> 4
D:0  D:1       D:2                  D:3
(D = Depth)

순으로 순회하게 됩니다.

활용

주로 미로찾기, 가중치가 없는 Graph 구조에서 최단 경로를 탐색할 때 사용됩니다. 또한 BFS의 특징처럼 Level(Depth) 별로 데이터(노드)를 탐색하는데 유용합니다. 혹은 어떤 행동의 최소 횟수 등을 찾는데에도 사용됩니다.

구현(Tree)

먼저 일반적인 Tree를 구현해봅시다.

설명을 위해 삭제, 수정 등의 메소드는 제외했습니다.

class TreeNode {
    var value: Int
    var childNodes: [TreeNode] = []
    
    init(value: Int) {
        self.value = value
    }
    
    func insert(node: TreeNode) {
        childNodes.append(node)
    }
}

 

위 숫자 Tree 이미지를 예제로 값을 넣어줍니다.

TreeNode만 사용해서 넣을 거기때문에 자식노드부터 차근차근 넣어줍니다.

let root = TreeNode(value: 2)
var tempNode0 = TreeNode(value: 6)
tempNode0.insert(node: TreeNode(value: 5))
tempNode0.insert(node: TreeNode(value: 11))
var tempNode1 = TreeNode(value: 7)
tempNode1.insert(node: TreeNode(value: 2))
tempNode1.insert(node: TreeNode(value: 10))
tempNode1.insert(node: tempNode0)
root.insert(node: tempNode1)
tempNode0 = TreeNode(value: 9)
tempNode0.insert(node: TreeNode(value: 4))
tempNode1 = TreeNode(value: 5)
tempNode1.insert(node: tempNode0)
root.insert(node: tempNode1)

코드가 보기 좀 그렇습니다.

 

일단 값들이 잘 삽입되었는지는 순회 구현을 통해 확인해보겠습니다.

위에서 언급했듯 Queue가 활용됩니다.

var search: [Int] = []
var queue: [TreeNode?] = []
var queuePointer = 0
func BFS(node: TreeNode) {
    queue.append(node) // 첫번째(Root) 노드를 Queue에 삽입
    while queuePointer < queue.count { // Queue가 비어있을 때까지 반복
        for i in queuePointer..<queue.count { // 현재 Queue 담긴 노드 하나씩 꺼내기
            if let node = queue[i] {
                queuePointer += 1 // Queue Pointer 값 + 1
                search.append(node.value) // 꺼낸(순회한) 노드 값 추가
                for childNode in node.childNodes { 자식 노드들을 다시 Queue에 추가
                    queue.append(childNode)
                }
            }
        }
    }
}

 

이제 돌아봅시다.

BFS(node: root)
print(search.map(String.init).joined(separator: " -> "))
// 2 -> 7 -> 5 -> 2 -> 10 -> 6 -> 9 -> 5 -> 11 -> 4

정상적으로 순회하는 것을 확인할 수 있습니다.

예제

실제 문제에서는 어떻게 사용될까요?

LeetCode에서 아주아주 Easy한 문제를 가져왔습니다.

https://leetcode.com/problems/same-tree/

DFS로도 풀 수 있지만 오늘은 BFS을 공부했으니 BFS로 풀어보겠습니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool {
        // 노드가 같은지 확인하는 로직
        var equal: (_ p: TreeNode?, _ q: TreeNode?) -> Bool = { p0, q0 in
            if p0?.val == q0?.val { return true }
            else { return false }
        }

        var queue: [(TreeNode?, TreeNode?)] = [(p, q)]
        var queuePointer = 0
        while queuePointer < queue.count {
            for i in queuePointer..<queue.count {
                queuePointer += 1
                if !equal(queue[i].0, queue[i].1) {
                    return false
                }
                
                // 둘 다 nil이면 비교할 필요도 Queue에 넣을 필요도 없음
                if (queue[i].0?.left != nil) || (queue[i].1?.left != nil) {
                    queue.append((queue[i].0?.left, queue[i].1?.left))
                }
                if (queue[i].0?.right != nil) || (queue[i].1?.right != nil) {
                    queue.append((queue[i].0?.right, queue[i].1?.right))
                }
            }
        }
        return true
    }
}

 

쉬운 문제였기 때문에 예제 코드 구조 그대로 사용이 가능했습니다.

하지만 현실(?)은 그렇지 않으니 LeetCode나 프로그래머스 같은 곳에서 BFS 키워드로 많은 문제를 접해보시기 바랍니다.

Conclusion

BFS는 특히 코딩 테스트에서 자주 사용되는 구조이기 때문에 익숙하게 활용할 수 있도록 이해하는 것이 중요합니다.

문제마다 문제 상황을 파악하고 BFS 구조로 탐색할 수 있는지 알아보는 연습도 해보시는 것도 추천드립니다.