백준 1991 트리 순회

출처: https://www.acmicpc.net/problem/1991

분류: 트리, 재귀

---

접근방식

기본적인 이진 트리 순회 문제입니다.

트리를 순회하는 방법은 대표적으로 preorder / inorder / postorder 방법이 있는데요,

이는 현재 노드를 언제 방문할건지가 기준이 됩니다.

preorder
현재 노드를 먼저 방문하겠다는 뜻입니다.

inorder
현재 노드를 중간에 방문하겠다는 뜻입니다.

postorder
현재 노드를 나중에 방문하겠다는 뜻입니다.

이 문제는 이진 트리이므로 왼쪽, 오른쪽을 재귀적으로 순회해주면서 언제 방문할지(print or 별도의 체크)만 결정해주면 됩니다.

 

해결방법

class Graph<T: Hashable> {
    var nodes = [T: Node]()
    
    class Node {
        var value: T
        var leftNode: Node?
        var rightNode: Node?
        
        init(_ value: T) {
            self.value = value
        }
    }
    
    func addChild(node: T, left: T?, right: T?) {
        if nodes[node] == nil {
            nodes[node] = Node(node)
        }
        if let left = left {
            nodes[node]?.leftNode = nodes[left, default: Node(left)]
        }
        if let right = right {
            nodes[node]?.rightNode = nodes[right, default: Node(right)]
        }
    }
    
    func preorder(at node: T, history: inout [T]) {
        history.append(node)
        if let left = nodes[node]?.leftNode {
            preorder(at: left.value, history: &history)

        }
        
        if let right = nodes[node]?.rightNode {
            preorder(at: right.value, history: &history)
        }
    }
    
    func inorder(at node: T, history: inout [T]) {
        if let left = nodes[node]?.leftNode {
            inorder(at: left.value, history: &history)
        }
        history.append(node)
        if let right = nodes[node]?.rightNode {
            inorder(at: right.value, history: &history)
        }
    }
    
    func postorder(at node: T, history: inout [T]) {
        if let left = nodes[node]?.leftNode {
            postorder(at: left.value, history: &history)
        }
        if let right = nodes[node]?.rightNode {
            postorder(at: right.value, history: &history)
        }
        history.append(node)
    }
}

var graph = Graph<Character>()
let n = Int(readLine()!)!
for _ in 0..<n {
    let input = readLine()!.split(separator: " ").map { $0 == "." ? nil : Character(String($0)) }
    graph.addChild(node: input[0]!, left: input[1], right: input[2])
}

var travel = [Character]()
graph.preorder(at: graph.nodes["A"]!.value, history: &travel)
print(String(travel))
travel.removeAll()
graph.inorder(at: graph.nodes["A"]!.value, history: &travel)
print(String(travel))
travel.removeAll()
graph.postorder(at: graph.nodes["A"]!.value, history: &travel)
print(String(travel))

배운점

구현하고 나니 어라? 루트는 어쩌지..? 하고 한참을 생각했네요...

문제에서는 순서도 보장되고 root가 무조건 "A"라고 주어지니 신경 안 쓰고 해도 되는 문제였어요!
그렇지 않다면 좀 귀찮아지긴하겠네요...!

그냥 복사하다가 postorder 재귀 안에서 inorder를 부르고 있더라는... 😂

눈 똑바로 뜨자.