[Swift 알고리즘] 프로그래머스(Lv.3) - 길 찾기 게임 / 2019 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 길 찾기 게임" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 길 찾기 게임

---

풀이

이번 문제는 이진 트리 문제입니다.

 

1. 노드를 y 기준으로 내림차순 정렬합니다.

노드의 y가 클수록 상위 depth 노드입니다.

append를 편하게 하기 위해 y 기준으로 내림차순 정렬해주었습니다.

 

2. 트리를 구현합니다.

직접 트리를 구현해야 합니다.

 

2-1. propery 

class Tree {
    var value: Int //노드 번호
    var x: Int //x 좌표
    var y: Int //y 좌표
    var leftChild: Tree? //왼쪽 자식 노드
    var rightChild: Tree? //오른쪽 자식 노드
    var parent: Tree? //부모 노드
    var description: String { //테스트용
        "x: \(x) / y: \(y)"
    }
    
    ...
}

 

이 문제는 이진 트리이기 때문에 leftChild, rightChild를 각각 선언했습니다.

 

2-2. 자식 추가 메서드

child를 추가하는 메서드입니다.

func addChild(_ node: Tree) {
    if node.x < self.x {
        if leftChild != nil {
            leftChild?.addChild(node)
        } else {
            leftChild = Tree(x: node.x, y: node.y, value: node.value)
            leftChild?.parent = self
        }
    } else {
        if rightChild != nil {
            rightChild?.addChild(node)
        } else {
            rightChild = Tree(x: node.x, y: node.y, value: node.value)
            rightChild?.parent = self
        }
    }
}

x를 비교하여 자신보다 작다면 left, 크다면 right에 삽입합니다.

만약 leftChild가 nil이 아니라면 nil인 자식이 나올 때까지 재귀 탐색합니다.

nil인 자식을 만났으면 노드를 생성하고 parent를 자신으로 선언합니다.

parent를 자신으로 선언한다는 의미가 곧 노드를 추가한다는 의미입니다.

 

right도 동일한 방법으로 수행합니다.

 

3. 트리를 생성합니다.

트리를 생성해야 합니다.

y 좌표를 기준으로 내림차순 정렬하였기 때문에 가장 앞 노드는 root 노드입니다.

root를 제외한 모든 노드를 addChild( )에 넣으면 x 좌표를 비교하며 알아서 배치가 됩니다.

let tree: Tree = nodes.first!    
for i in 1..<nodes.count {
    let node = nodes[i]
    tree.addChild(node)
}

 

4. 전위순회, 후위순회 합니다.

재귀를 이용해 트리를 순회합니다.

재귀를 이용한 전형적인 순회 방법을 사용하였습니다.

 

5. 결과를 return 합니다.

4에서 구한 순회 결과를 return 합니다.

 

후기

Swift를 이용해서 트리를 구현해보지 않아 생각보다 오래 걸렸습니다.

머리 속으로는 그려지는데 코드로는 작성이 잘 안 될 때 너무 답답한 것 같습니다.

 

감사합니다!

---

전체 코드

import Foundation

class Tree {
    var value: Int
    var x: Int
    var y: Int
    var leftChild: Tree?
    var rightChild: Tree?
    var parent: Tree?
    var description: String {
        "x: \(x) / y: \(y)"
    }
    
    init(x: Int, y: Int, value: Int) {
        self.x = x
        self.y = y
        self.value = value
    }
    
    func addChild(_ node: Tree) {
        if node.x < self.x {
            if leftChild != nil {
                leftChild?.addChild(node)
            } else {
                leftChild = Tree(x: node.x, y: node.y, value: node.value)
                leftChild?.parent = self
            }
        } else {
            if rightChild != nil {
                rightChild?.addChild(node)
            } else {
                rightChild = Tree(x: node.x, y: node.y, value: node.value)
                rightChild?.parent = self
            }
        }
    }
}

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

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

    return values
}

func solution(_ nodeinfo:[[Int]]) -> [[Int]] {
    var nodes: [Tree] = []
    for node in nodeinfo {
        let treeNode = Tree(x: node[0], y: node[1], value: nodes.count+1)
        nodes.append(treeNode)
    }
    nodes.sort { $0.y > $1.y }
    
    let tree: Tree = nodes.first!    
    for i in 1..<nodes.count {
        let node = nodes[i]
        tree.addChild(node)
    }
    
    let pre = preOrder(tree)
    print("pre: \(pre)")
    
    let post = postOrder(tree)
    print("post: \(post)")
    
    return [pre, post]
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.