[Swift 알고리즘] 백준 BOJ - 1991 트리 순회

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

 

오늘은 "백준 BOJ - 1991 트리 순회" 문제를 풀었습니다.

 

---

Github

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

 

문제 링크

1991번: 트리 순회

 

---

풀이

이번 문제는 트리 순회 문제입니다.

트리를 순회하는 방법에 따라 다른 노드 방문 순서를 출력하면 되는데요.

전위, 중위, 후위 순서로 출력을 하는 문제입니다.

 

트리의 전위, 중위, 후위에 대해 이해하고 dfs의 재귀를 이용할 줄 알면 쉽게 해결할 수 있습니다.

 

전위 순회는 root를 먼저 방문하고 왼쪽 노드, 오른쪽 노드 순서로 방문하는 방법입니다.

따라서 왼쪽 노드를 이동하기 전에 node를 출력하면 전위 순회 순서로 출력할 수 있습니다.

 

중위 순회는 왼쪽 하위 노드를 방문하고 root, 오른쪽 노드 순서로 방문하는 방법입니다.

따라서 오른쪽 노드를 방문하기 전에 node를 출력하면 중위 순회 순서로 출력할 수 있습니다.

 

후위 순회는 root의 모든 하위 노드를 방문하고 root를 방문하는 방법입니다. 즉 왼쪽, 오른쪽, root 순서로 방문합니다.

따라서 왼쪽, 오른쪽을 방문한 후에 node를 출력하면 후위 순회 순서로 출력할 수 있습니다.

 

저는 dfs()를 세 개 만들기 귀찮아서 result를 배열로 만들어 구현했습니다.

 

---

전체 코드

//1991 트리 순회
import Foundation

let count = Int(readLine()!)!
var results: [String] = ["", "", ""]
var tree: [String:[String]] = [:]
for _ in 0..<count {
    let input = readLine()!.split { $0 == " " }.map { String($0) }
    tree.updateValue([input[1], input[2]], forKey: input[0])
}

func dfs(_ node: String) {
    if node == "." {
        return
    }
    
    results[0] += node
    dfs(tree[node]![0])
    results[1] += node
    dfs(tree[node]![1])
    results[2] += node
}

dfs("A")

for result in results {
    print(result)
}

---

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

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

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