스위프트 코딩테스트 강좌, 트리의 부모 찾기

컴퓨터 과학에서 트리는 계층적 데이터 구조의 한 종류로, 노드로 이루어진 그래프의 일종입니다. 본 강좌에서는 스위프트를 사용하여 주어진 노드의 부모 노드를 찾는 알고리즘 문제를 해결해 보겠습니다.

문제 설명

주어진 이진 트리에서 특정 노드의 부모 노드를 찾는 함수를 작성하시오. 트리는 다음과 같은 방식으로 표현됩니다. 


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

위와 같은 구조체가 주어질 것입니다. 이 구조체를 사용하는 이진 트리에서 특정 노드의 부모 노드를 찾는 `findParent` 함수를 구현합니다.

함수 시그니처


func findParent(root: TreeNode?, target: Int) -> Int?

입력

  • root: 이진 트리의 루트 노드 (TreeNode? 타입)
  • target: 부모를 찾고자 하는 노드의 값 (Int 타입)

출력

주어진 노드의 부모 노드의 값. 만약 주어진 노드가 존재하지 않거나 루트 노드가 대상인 경우에는 nil을 반환합니다.

예제

만약 다음과 같은 이진 트리가 있다고 가정합니다:

            1
          /   \
         2     3
        / \   / \
       4   5 6   7

    findParent(root: rootNode, target: 5) ➔ 2
    findParent(root: rootNode, target: 1) ➔ nil
    findParent(root: rootNode, target: 8) ➔ nil

알고리즘 설계

부모 노드를 찾기 위해서는 이진 트리를 탐색해야 합니다. 일반적인 탐색 알고리즘인 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)을 사용할 수 있습니다. 여기서는 DFS를 이용하여 재귀적으로 트리를 탐색하는 방법을 채택하겠습니다.

DFS 탐색 방법

  • 현재 노드가 nil인 경우 탐색 종료
  • 현재 노드의 값이 target과 일치하는지 확인
  • 일치하면 현재 노드의 부모 값을 반환
  • 일치하지 않으면 왼쪽 및 오른쪽 자식 노드로 재귀 호출

구현

이제 위의 알고리즘을 바탕으로 함수 findParent를 구현해보겠습니다.


func findParent(root: TreeNode?, target: Int) -> Int? {
    return findParentHelper(root, target: target, parent: nil)
}

private func findParentHelper(_ node: TreeNode?, target: Int, parent: TreeNode?) -> Int? {
    guard let node = node else { return nil } // 현재 노드가 nil인 경우

    if node.value == target {
        return parent?.value // 부모 노드를 반환
    }

    // 왼쪽 자식 탐색
    let leftResult = findParentHelper(node.left, target: target, parent: node)
    if leftResult != nil {
        return leftResult // 왼쪽에서 부모를 찾았다면 반환
    }

    // 오른쪽 자식 탐색
    return findParentHelper(node.right, target: target, parent: node)
}

테스트

이제 구현한 함수를 테스트하여 올바르게 작동하는지 확인하겠습니다.


let rootNode = TreeNode(value: 1)
rootNode.left = TreeNode(value: 2)
rootNode.right = TreeNode(value: 3)
rootNode.left?.left = TreeNode(value: 4)
rootNode.left?.right = TreeNode(value: 5)
rootNode.right?.left = TreeNode(value: 6)
rootNode.right?.right = TreeNode(value: 7)

print(findParent(root: rootNode, target: 5) ?? "nil") // 2
print(findParent(root: rootNode, target: 1) ?? "nil") // nil
print(findParent(root: rootNode, target: 8) ?? "nil") // nil

결론

이번 강좌에서는 스위프트로 이진 트리에서 특정 노드의 부모를 찾는 알고리즘을 구현해보았습니다. 트리 구조의 탐색 문제에서 DFS의 기본 개념을 적용하여 코드를 작성하는 방법을 배쳤습니다.
이러한 문제를 통해 트리에 대한 이해와 재귀적인 사고를 키울 수 있습니다.

추가적으로 트리의 다른 속성에 대한 문제도 풀어보며 실력을 쌓길 바랍니다.