이진 트리 유형 (BFS)

BFS

https://leetcode.com/

• DFS에서는 깊이를 우선시했지만, 너비 우선 탐색(BFS)에서는 너비를 우선시 함
• 노드의 깊이는 루트부터 해당 노드까지의 거리임. 따라서 DFS에서는 리프 노드에 도달할 때까지 탐색했음
• 반면, BFS에서는 다음 깊이로 이동하기 전에 같은 레벨에 있는 모든 노드를 먼저 탐색함
  • 예를 들어, 위 트리를 BFS하면 0, 1, 2, 3, 4, 5, 6, 7, 8 순서로 노드를 탐색함
• DFS는 재귀를 사용했지만, BFS는 반복문을 사용함

 

BFS와 DFS를 언제 사용할까?

• 많은 문제는 모든 노드를 방문하는 것이 중요하기 때문에 DFS, BFS 어떤 것을 사용해도 크게 문제되지 않음
• DFS는 재귀를 사용하기 때문에 코드가 간결하고, 구현이 쉬움
• 하지만 노드를 레벨에 따라 처리하고자 하는 문제에서는 BFS의 사용이 더 적절한 알고리즘임

 

DFS의 단점

• 값을 찾기 위해 많은 시간을 낭비할 수 있음
  • 예를 들어, 큰 트리가 있고, 루트의 오른쪽 자식에 저장된 값을 찾고 있다고 가정해보자
  • 그럼 왼쪽 서브트리를 굳이 탐색할 필요없이 오른쪽으로 한 번만 이동하면 끝임
  • 하지만 왼쪽을 우선시하는 DFS를 수행할 경우, 전체 왼쪽 서브트리를 탐색하게 되므로 많은 연산이 필요할 수 있음

BFS의 단점

• 찾고자 하는 노드가 아래쪽에 있을 경우, 아래로 내려가기 전 모든 레벨을 탐색해야 함
• 이것이 비효율적인 연산일 수 있다.

공간 복잡도

• DFS는 트리의 높이와 선형적으로 공간을 사용함
• BFS는 레벨 내의 노드와 선형적으로 공간을 사용함
• 더 많은 쪽이 더 많은 공간을 차지함
• 만약 편향된 트리(직선)가 있다면, BFS는 O(1)이지만, DFS는 O(n)이 된다. 하지만 편향된 트리는 드물어요!

 

BFS 코드 구현

가장 일반적인 BFS 코드

func printAllNodes(_ root: TreeNode?) {
    guard let root = root else { return }
    
    var queue: [TreeNode] = [root]
    
    while !queue.isEmpty {
        let nodesInCurrentLevel = queue.count
        
        // 현재 레벨에 대한 로직 수행
        
        for _ in 0 ..< nodesInCurrentLevel {
            let node = queue.removeFirst()
            
            // 현재 노드에 대한 로직을 수행
            print(node.val)
            
            // 다음 레벨을 큐에 넣기
            if let leftNode = node.left {
                queue.append(leftNode)
            }
            
            if let rightNode = node.right {
                queue.append(rightNode)
            }
        }
    }
}

 

• 각 while 루프에서 큐는 현재 레벨의 모든 노드가 포함되어 있음
• 다음 for 루프를 통해 현재 레벨의 모든 노드를 탐색함
• 효율적인 큐를 사용한다고 가정했을 때, dequeue나 enqueue의 연산은 O(1)이므로 BFS의 연산은 O(n) 시간 복잡도를 가진다.

 

예제 1

• 이진 트리의 루트가 주어졌을 때, 트리의 오른쪽에서 본 것처럼 노드의 값을 위에서 아래로 순서대로 반환하세요.

 

예시 1

• root = [1, 2, 3, null, 5, null, 4]
• 정답: [1, 3, 4]

 

방법

• 각 레벨에서 가장 오른쪽에 있는 노드를 구하면 됨
• BFS를 수행하면, 각 while 루프는 전체 레벨의 배열을 가지게 된다.
• 왼쪽 자식을 오른쪽 자식보다 우선하여 탐색하면, 각 반복의 가장 오른쪽에 있는 노드가 해당 값을 가지게 됨

class Solution {
    func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        var queue = [root]
        var ans: [Int] = []

        while !queue.isEmpty {
            let nodesInCurrentLevel = queue.count
            ans.append(queue[nodesInCurrentLevel - 1].val)

            for _ in 0 ..< nodesInCurrentLevel {
                let node = queue.removeFirst()

                if let left = node.left {
                    queue.append(left)
                }

                if let right = node.right {
                    queue.append(right)
                }
            }
        }

        return ans
    }
}

 

• 알고리즘의 시간 및 공간 복잡도는 O(n)
• 각 노드를 한 번만 방문하고, 각 노드에서 일정한 작업을 수행함 (시간)
• 큐는 최대 O(n) 노드를 포함할 수 있음 (공간)

 

 

예제 2

• 주어진 이진 트리의 루트를 기준으로, 트리의 각 행(row)에서 가장 큰 값을 배열로 반환하세요.

 

예시 1

• root = [1, 3, 2, 5, 3, null, 9]
• 정답: [1, 3, 9]

 

방법

• 이진 트리에서 행은 레벨과 같은 의미.
• 따라서 while 루프는 각 레벨을 나타내는 것과 동일하다.
• 각 레벨에서 가장 큰 값을 찾기 위해 정수 currMax를 사용하여 구현이 가능

class Solution {
    func largestValues(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        var queue = [root]
        var ans: [Int] = []

        while !queue.isEmpty {
            let nodesInCurrentLevel = queue.count
            var currMax = Int.min

            for _ in 0 ..< nodesInCurrentLevel {
                let node = queue.removeFirst()

                currMax = max(currMax, node.val)

                if let left = node.left {
                    queue.append(left)
                }

                if let right = node.right {
                    queue.append(right)
                }
            }

            ans.append(currMax)
        }

        return ans
    }
}

 

• 시간 및 공간 복잡도는 O(n)임

 

Reference

• https://leetcode.com/