Programmers Lv3) [2019 카카오블라인드] 길 찾기 게임

출처: programmers.co.kr/learn/courses/30/lessons/42892

분류: Tree

---

접근방식

주어진 노드 정보를 가지고 이진트리를 구성한 후 전위순회, 후위순회 결과를 반환하면 되는 문제였습니다.

노드 정보는 [Int]로 x, y 값이 주어지는데, 같은 레벨의 노드는 모두 y값이 같고, y값이 클수록 상위 레벨의 노드입니다.

 따라서 y값을 기준으로 sort해주고 차례대로 이진트리를 구성해주면 됩니다.

저는 순회할 때 인덱스를 반환해야 하므로, 노드에 index 값을 가지고 있도록 했습니다. x,y 정보도 그냥 배열 그대로 들고있도록 해줬어요.

class Tree {
    var value: [Int]
    var index: Int
    var leftChild: Tree?
    var rightChild: Tree?
    weak var parents: Tree?
}

 

그리고 배열을 enumerated()를 해서 sort를 해줬는데, 그정보를 그대로 넘겨받도록

EnumeratedSequence<[[Int]]>.Element 를 그대로 입력 받아서 사용했습니다.

init(_ info: EnumeratedSequence<[[Int]]>.Element) {
  self.index = info.offset+1
  self.value = info.element
}

 

그리고 입력은 문제가 없는 이진트리가 온다고 했고, sort를 해줬기 때문에 x값만 가지고 왼쪽인지 오른쪽인지 판단해줬습니다.

자식이 없다면 그대로 넣어주고 있다면 재귀적으로 자식의 노드에 추가해주도록 했습니다.

func addChild(_ info: EnumeratedSequence<[[Int]]>.Element) {
    if  info.element[0] < value[0] {
        guard leftChild != nil else {
            leftChild = Tree(info)
            leftChild?.parents = self
            return
        }
        leftChild?.addChild(info)
    } else {
        guard rightChild != nil else {
            rightChild = Tree(info)
            rightChild?.parents = self
            return
        }
        rightChild?.addChild(info)
    }
}

 

순회도 정통적인 방식 대로 재귀적으로 구현해주면 됩니다.

func preOrder(_ tree: Tree) -> [Int] {
    var result = [tree.index]
    
    if let leftChild = tree.leftChild {
        result.append(contentsOf: preOrder(leftChild))
    }
    if let rightChild = tree.rightChild {
        result.append(contentsOf: preOrder(rightChild))
    }
    
    return result
}

func postOrder(_ tree: Tree) -> [Int] {
    var result = [Int]()
    
    if let leftChild = tree.leftChild {
        result.append(contentsOf: postOrder(leftChild))
    }
    if let rightChild = tree.rightChild {
        result.append(contentsOf: postOrder(rightChild))
    }
    
    result.append(tree.index)

    return result
}

 

 

크게 꼬아놓은 부분이 없어서 그대로 구현하면 되는 문제였네요.

 

해결방법

import Foundation

class Tree {
    var value: [Int]
    var index: Int
    var leftChild: Tree?
    var rightChild: Tree?
    weak var parents: Tree?
    
    init(_ info: EnumeratedSequence<[[Int]]>.Element) {
        self.index = info.offset+1
        self.value = info.element
    }
    
    func addChild(_ info: EnumeratedSequence<[[Int]]>.Element) {
        if  info.element[0] < value[0] {
            guard leftChild != nil else {
                leftChild = Tree(info)
                leftChild?.parents = self
                return
            }
            leftChild?.addChild(info)
        } else {
            guard rightChild != nil else {
                rightChild = Tree(info)
                rightChild?.parents = self
                return
            }
            rightChild?.addChild(info)
        }
    }
}

func preOrder(_ tree: Tree) -> [Int] {
    var result = [tree.index]
    
    if let leftChild = tree.leftChild {
        result.append(contentsOf: preOrder(leftChild))
    }
    if let rightChild = tree.rightChild {
        result.append(contentsOf: preOrder(rightChild))
    }
    
    return result
}

func postOrder(_ tree: Tree) -> [Int] {
    var result = [Int]()
    
    if let leftChild = tree.leftChild {
        result.append(contentsOf: postOrder(leftChild))
    }
    if let rightChild = tree.rightChild {
        result.append(contentsOf: postOrder(rightChild))
    }
    
    result.append(tree.index)

    return result
}


func solution(_ nodeinfo:[[Int]]) -> [[Int]] {
    
    let sortedNodeInfos = nodeinfo.enumerated().sorted(by: { $0.element[1] > $1.element[1] })
    let tree = Tree(sortedNodeInfos[0])
    
    for info in sortedNodeInfos.dropFirst() {
        tree.addChild(info)
    }
    
    var result = [[Int]]()
    result.append(preOrder(tree))
    result.append(postOrder(tree))
    
    return result
}

 

배운점

확실히 최근 문제보다 예전 문제가 수월한 느낌이다.