스위프트 코딩테스트 강좌, 이진 트리

안녕하세요! 오늘은 이진 트리와 관련된 코딩 테스트 문제를 해결해보겠습니다. 이진 트리는 특히 많은 문제에서 자주 등장하는 자료구조입니다. 이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조로, 다양한 방식으로 탐색할 수 있습니다. 우리의 목표는 이진 트리를 이해하고, 이를 활용하여 특정 문제를 해결하는 것입니다.

문제 설명

다음과 같은 이진 트리가 주어졌을 때, 모든 노드를 DFS(깊이 우선 탐색) 방식으로 순회하여 노드의 값을 리스트로 반환하는 함수를 작성하시오.

문제 정의

func depthFirstTraversal(root: TreeNode?) -> [Int] {}

입력: 이진 트리의 루트 노드인 root

출력: DFS 순회 결과로 노드의 값을 담고 있는 정수 배열

예시

입력:

출력:

[1, 2, 4, 5, 3]

이진 트리의 정의

이진 트리는 두 개의 자식 노드를 가질 수 있는 트리 구조입니다. 각 노드는 값을 가지고 있으며, 이진 트리는 보통 재귀적으로 정의됩니다. 노드가 비어있을 수도 있으므로, 루트 노드를 nil로 처리해야 합니다.

문제 풀이 과정

이 문제를 해결하기 위해, DFS 방식으로 트리를 탐색할 것입니다. DFS는 깊이 우선 탐색 방법으로, 한 쪽 가지를 완전히 제어한 후 다음 가지로 넘어가는 방식을 의미합니다. 아래는 DFS를 이용한 트리 순회의 과정을 설명합니다.

1단계: 트리 노드 정의

먼저, 트리 노드를 정의해야 합니다. 트리 노드를 정의하기 위해 TreeNode 클래스를 구현하겠습니다.


    class TreeNode {
        var value: Int
        var left: TreeNode?
        var right: TreeNode?
        
        init(value: Int) {
            self.value = value
        }
    }

2단계: DFS 함수 구현

이제 DFS 방식으로 이진 트리를 탐색하는 함수를 구현하겠습니다. 우선순위는 현재 노드 -> 왼쪽 자식 -> 오른쪽 자식입니다. 우리는 재귀적으로 이를 수행할 것입니다.


    func depthFirstTraversal(root: TreeNode?) -> [Int] {
        guard let node = root else { return [] }
        
        // 현재 노드의 값을 배열에 추가
        var result = [node.value]
        
        // 왼쪽 서브트리 탐색
        result += depthFirstTraversal(root: node.left)
        
        // 오른쪽 서브트리 탐색
        result += depthFirstTraversal(root: node.right)
        
        return result
    }

3단계: 테스트 및 검증

이제 구현한 함수를 테스트하기 위해 이진 트리를 생성해보겠습니다. 위의 예시를 사용하여 트리를 생성하겠습니다.


    let root = TreeNode(value: 1)
    let leftChild = TreeNode(value: 2)
    let rightChild = TreeNode(value: 3)
    let leftLeftChild = TreeNode(value: 4)
    let leftRightChild = TreeNode(value: 5)
    
    root.left = leftChild
    root.right = rightChild
    leftChild.left = leftLeftChild
    leftChild.right = leftRightChild
    
    let result = depthFirstTraversal(root: root)
    print(result)  // [1, 2, 4, 5, 3]

결론

이진 트리를 탐색하는 DFS 알고리즘을 구현했습니다. 이 문제를 통해 이진 트리의 구조와 DFS 탐색의 개념을 이해할 수 있었습니다. 스위프트에서는 재귀를 통해 트리를 쉽게 탐색할 수 있으며, 이와 같은 문제는 코딩 테스트에서 자주 나오는 유형이므로 연습하는 것이 중요합니다. 다음 시간에는 또 다른 알고리즘 문제를 탐구해 보겠습니다. 감사합니다!