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

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

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

 

 

단계는 총 두 가지입니다.

1. 주어진 배열을 아래 그림과 같이 정렬하기

// [x, y, value]
    var nodes: [[Int]] = nodeinfo.enumerated().map {
        length = max(length, $0.element[0])
        return [$0.element[0], $0.element[1], $0.offset + 1]
    }.sorted(by: { $0[1] == $1[1] ? $0[0] < $1[0] : $0[1] > $1[1] })

저는 nodes라는 배열을 새로 만들어서 주어진 nodeinfo를 기존의 x, y 좌표와 값인 index + 1을 넣어주고 y가 높은 순으로 정렬하고 만약 y값이 같다면 x가 적은 순으로 정렬하도록 하였습니다.

 

 

2. Node 클래스를 만들어 연결하기

public class BinaryNode {
    public var value: Int
    public var location: [Int] // 좌표
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
}

 

 

이 BinaryNode 클래스에 addChild라는 함수를 추가합니다. 

node를 받으면 x값을 보고 현재 위치보다 작으면 왼쪽, 크면 오른쪽을 탐색합니다.

만약 현재 노드(cur)의 leftChild 혹은 rightChild가 비었다면 삽입하고 return합니다. 이미 있다면 현재 노드(cur)를 현재 노드(cur)의 leftChild 혹은 rightChild로 변경합니다.

    public func addChild(_ node: [Int]) {
        var cur = self
        
        while true {
            if cur.location[0] > node[0] { // 왼쪽
                if cur.leftChild != nil {
                    cur = cur.leftChild!
                } else {
                    let newNode = BinaryNode(node: node)
                    cur.leftChild = newNode
                    return
                }
            } else {
                if cur.rightChild != nil {
                    cur = cur.rightChild!
                } else {
                    let newNode = BinaryNode(node: node)
                    cur.rightChild = newNode
                    return
                }
            }
        }
    }

 

 

아래의 그림으로 설명하자면, 현재 7, 4, 2를 삽입하였고 6을 삽입해야 되는 상황으로 가정합니다.

BinaryNode(7).addChild(BinaryNode(6))을 합니다.

 

- cur = BinaryNode(7), node = BinaryNode(6)

BinaryNode(6)의 x위치는 1이고 BinaryNode(7)의 x위치는 8이기에 BinaryNode(7)의 왼쪽을 탐색합니다.

BinaryNode(7)의 왼쪽에는 BinaryNode(4)가 존재하기에 cur을 BinaryNode(4)로 업데이트합니다.

 

- cur = BinaryNode(4), node = BinaryNode(6)

BinaryNode(6)의 x위치는 1이고  BinaryNode(4)의 x위치는 3이기에 BinaryNode(4)의 왼쪽을 탐색합니다.

BinaryNode(4)의 왼쪽은 nil입니다! BinaryNode(4)의 왼쪽을 BinaryNode(6)로 업데이트하고 함수를 종료합니다.

 

 

 

그렇게 왼쪽, 오른쪽에 삽입하다보면 아래와 같은 결과가 나옵니다.

전위순위와 후위순위에 대한 설명은 생략합니다.

 

import Foundation

public class BinaryNode {
    public var value: Int
    public var location: [Int] // 좌표
    public var leftChild: BinaryNode?
    public var rightChild: BinaryNode?
    
    public init(node: [Int]) {
        self.value = node[2]
        self.location = [node[0], node[1]]
    }
    
    public func addChild(_ node: [Int]) {
        var cur = self
        
        while true {
            if cur.location[0] > node[0] { // 왼쪽
                if cur.leftChild != nil {
                    cur = cur.leftChild!
                } else {
                    let newNode = BinaryNode(node: node)
                    cur.leftChild = newNode
                    return
                }
            } else {
                if cur.rightChild != nil {
                    cur = cur.rightChild!
                } else {
                    let newNode = BinaryNode(node: node)
                    cur.rightChild = newNode
                    return
                }
            }
        }
    }
    
    public func preOrder(action: ((Int) -> Void)) {
        action(value)
        leftChild?.preOrder(action: action)
        rightChild?.preOrder(action: action)
    }
    
    public func postOrder(action: ((Int) -> Void)) {
        leftChild?.postOrder(action: action)
        rightChild?.postOrder(action: action)
        action(value)
    }
}

func solution(_ nodeinfo:[[Int]]) -> [[Int]] {
    var length = 0
    
    // [x, y, value]
    var nodes: [[Int]] = nodeinfo.enumerated().map {
        length = max(length, $0.element[0])
        return [$0.element[0], $0.element[1], $0.offset + 1]
    }.sorted(by: { $0[1] == $1[1] ? $0[0] < $1[0] : $0[1] > $1[1] })
    
    let root = BinaryNode(node: nodes.removeFirst())
    
    for node in nodes {
        root.addChild(node)
    }
    
    var result = Array(repeating: [Int](), count: 2)
    root.preOrder(action: { result[0].append($0) })
    root.postOrder(action: { result[1].append($0) })
    
    return result
}

print(solution([[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]])) // [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]]