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

문제 소개

프로그래머스 - 길 찾기 게임 (이진 트리 순회 문제)

프로그래머스

 

이번 문제는 이진 트리 순회 문제였다. 아래와 같은 트리 순회방법이 네가지가 있는데, 여기서는 전위 순회, 후위 순회를 물어보는 문제였다.

출처: 위키피디아

예를 들면 [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]] 형태로 출력되면 된다.

출처: 프로그래머스

 

 

풀이 방법

다행히 문제에서 모든 노드의 x 좌표의 값은 다르다고 명시해줬기 때문에 모든 노드를 노드번호와 함께 x 에 대한 오름차순으로 정렬해 주었다. 그렇게 되면 y 값에 따라 왼쪽, 오른쪽으로 나눌 수 있게 된다.

 

전위 순회

그 후 순회를 Root 를 기준으로 왼쪽, 오른쪽을 구분해주고 왼쪽에서의 Root 를 구한 뒤, 오른쪽에서의 Root 를 구하는 식으로 구조를 짰고, 재귀함수를 활용했다.

 

후위 순회

전위 순회의 반대이다. 전위 순회를 마치고 역순으로 결과를 넣어준다.

 

import Foundation

// Node 구조체 생성
struct Node {
    var num: Int
    var x: Int
    var y: Int
}

func solution(_ nodeinfo:[[Int]]) -> [[Int]] {
    var nodes = [Node]()
    var result: [[Int]] = [[], []]
    
    for (index, nodeinfo) in nodeinfo.enumerated() {
        let newNode = Node(num: index+1, x: nodeinfo[0], y: nodeinfo[1])
        nodes.append(newNode)
    }
    
    // x 오름차순 정렬
    nodes = nodes.sorted(by: { $0.x < $1.x })
    
    func traversal(_ nodes: [Node]) {
        var num = 0
        var rootIndex = 0
        var y = -1
        
        if nodes.isEmpty { return }
        
        for (index, node) in nodes.enumerated() {
            if node.y > y {
                num = node.num
                rootIndex = index
                y = node.y
            }
        }
        
        // 전위 순회 결과
        result[0].append(num)
        
        // 왼쪽 탐색
        if rootIndex > 0 {
            let left = Array(nodes[..<rootIndex])
            traversal(left)
        }
        
        // 오른쪽 탐색
        if rootIndex < nodes.count {
            let right = Array(nodes[(rootIndex+1)...])
            traversal(right)
        }
        
        // 후위 순회 결과
        result[1].append(num)
    }
    
    // 탐색 시작
    traversal(nodes)
        
    return result
}