[프로그래머스] Swift - 길 찾기 게임

https://school.programmers.co.kr/learn/courses/30/lessons/42892

프로그래머스

 

2023.08.07 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

우선 문제에서부터 트리 구조라는 것을 알려주고 있습니다.

따라서 트리 자료구조를 활용해야 합니다.

 

• 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값 보다 작다.
• 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값 보다 크다.

이 조건으로 인해 트리는 이진 탐색 트리(BST)로 구체화될 수 있습니다.

 

BST (Binary Search Tree)

• 각 노드가 서로 구별되는 데이터를 가진다.
• 각 데이터들은 크기를 비교할 수 있다.
• 기준 노드보다 작은 것들은 left subtree로 큰 것들은 right subtree로 분리할 수 있다.

 

BST의 조건에 이번 문제가 정확히 들어 맞습니다.

여기서 데이터는 문제에서의 x 좌표에 해당됩니다. (x 값을 기준으로 비교하여 subtree를 구성하기 때문)

 

문제 풀이 순서

1. x 좌표를 데이터로 하는 Binary Search Tree를 구현
2. node들을 전부 insert
3. 전위 순회, 후위 순회 구현
4. 정답 리턴

이렇게 문제 풀이를 진행했습니다.

 

우선 BST를 구현해야 하는데 BST 자체는 일반적인 BST를 구현하면 됩니다.

트리의 함수에는 insert만 구현했습니다. (remove와 같은 기능 필요 X)

 

트리의 노드를 구현할 때는 1가지를 더 추가해야 했습니다.

바로 노드의 인덱스 입니다. 

저는 name이라는 이름의 프로퍼티로 이것을 추가했습니다.

문제에서 nodeinfo[i]는 i+1번 노드의 좌표라고 조건을 제시하고 있으며 문제의 result에서 트리 탐색의 결과로 이 i+1 값들을 출력하고 있습니다.

따라서, tree에 노드를 insert할 때 위치 비교는 x 좌표(data)로 하지만 출력은 index로 해야하는 상황이기 때문에 이 2가지를 모두 노드가 가지고 있어야 했습니다.

 

이렇게 BST를 구현하고 나서 nodeinfo의 노드들을 트리에 insert해야 하는데 여기서 주의해야 할 점이 있습니다..!

바로 y좌표 입니다.

 

주어진 입출력 예시가 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] 일 때,

이 순서대로 insert를 진행하면 트리의 root가 [5, 3]이 됩니다.

하지만 문제 조건에서 y좌표가 큰 노드가 더 상단에 위치해야 한다고 제시하고 있습니다.

이진 트리의 구조는 위의 사진과 같습니다. 여기서 상단이라고 표현한 것은 더 낮은 Level을 의미합니다.

 

따라서, 우리는 y좌표가 큰 것들을 먼저 insert 해야 합니다. ➡️ nodeinfo를 y좌표의 내림차순으로 정렬해야 한다는 결론 도출

 

하지만 정렬을 곧바로 하게 되면 문제가 발생합니다.

우리는 nodeinfo의 인덱스를 노드의 이름으로 정해서 출력을 해야하는데 정렬을 하게 되면 이 index가 섞이기 때문입니다.

따라서, nodeinfo의 정렬 후에도 초기의 index값을 알 수 있어야 합니다. ➡️ nodeinfo의 정렬 전에 index를 각 노드 정보에 추가해서 저장하자

 

코드로 나타내면 다음과 같습니다.

let nodeinfo: [[Int]] = nodeinfo.map {
    index += 1
    return $0 + [index]
}.sorted {
    $0[1] > $1[1]   // y좌표를 내림차순으로 정렬해야 y좌표가 큰 노드가 트리의 상단에 위치하게 된다.
}

여기서 nodeinfo의 타입을 [[Int]]로 명시해주고 있습니다.

Xcode에서 풀 때는 컴파일러가 타입 추론을 해주어서 생략했을 때도 문제가 없었지만 프로그래머스에서 채점을 받을 때에는 타입 추론 기능이 Xcode보다 부실한지 에러가 발생했습니다.

 

컴파일 에러 발생 -> 타입을 직접 명시해서 해결

 

아무튼!

이렇게 nodeinfo를 가공을 한 뒤 BST에 전부 insert 하면 자동으로 문제에서 제시한 구조로 저장되게 됩니다.

 

이제 전위 순회와 후위 순회만 구현하면 되는데 이것들은 재귀 함수로 구현하면 편리합니다.

풀이의 코드를 참고해주세요!

 

풀이

1. Node 클래스 구현

fileprivate class Node {
    var name: Int   // nodeinfo의 인덱스에 1을 더한 값
    var data: Int   // x 좌표
    var left: Node?
    var right: Node?

    init(name: Int, data: Int, left: Node? = nil, right: Node? = nil) {
        self.name = name
        self.data = data
        self.left = left
        self.right = right
    }
}

 

2. BinarySearchTree 구현

fileprivate struct BinarySearchTree {
    private var root: Node?
    
    init() {}
    
    // O(logN)
    mutating func insert(name: Int, data: Int) {
        let newNode = Node(name: name, data: data)
        self.root = self.insert(from: root, newNode: newNode)
    }
    
    private mutating func insert(from node: Node?, newNode: Node) -> Node {
        guard let node = node else {
            return newNode
        }
        
        if newNode.data < node.data {
            node.left = insert(from: node.left, newNode: newNode)
        } else {
            node.right = insert(from: node.right, newNode: newNode)
        }
        
        return node
    }
    
    // O(N)
    func preorder() -> [Int] {
        var result = [Int]()
        self.preorder(node: self.root, result: &result)
        return result
    }
    
    private func preorder(node: Node?, result: inout [Int]) {
        guard let node = node else { return }
        result.append(node.name)
        preorder(node: node.left, result: &result)
        preorder(node: node.right, result: &result)
    }
    
    // O(N)
    func postorder() -> [Int] {
        var result = [Int]()
        self.postorder(node: self.root, result: &result)
        return result
    }
    
    private func postorder(node: Node?, result: inout [Int]) {
        guard let node = node else { return }
        postorder(node: node.left, result: &result)
        postorder(node: node.right, result: &result)
        result.append(node.name)
    }
}

 

3. solution 함수 구현

fileprivate func solution(_ nodeinfo:[[Int]]) -> [[Int]] {
    // Binary Search Tree 문제
    
    var index = 0
    
    let nodeinfo: [[Int]] = nodeinfo.map {
        index += 1
        return $0 + [index]
    }.sorted {
        $0[1] > $1[1]   // y좌표를 내림차순으로 정렬해야 y좌표가 큰 노드가 트리의 상단에 위치하게 된다.
    }

    var bst = BinarySearchTree()
    
    for node in nodeinfo {
        let data = node[0]
        let name = node[2]
        
        bst.insert(name: name, data: data)
    }
    
    let preorderResult = bst.preorder()
    let postorderResult = bst.postorder()
    
    return [preorderResult, postorderResult]
}

 

마무리

오랜만에 자료구조 문제였습니다.

BST에 대한 개념에 대해 최근에 다시 공부를 했어서 바로 떠올려 구현을 시작할 수 있었습니다.

그래도 y좌표 정렬과 트리 노드의 구성에 name 필드 추가 등 디테일한 부분에서 추가적인 사고가 필요했던 문제였습니다!