[BOJ] 백준 1991 트리 순회 (Swift)

문제

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

1991번: 트리 순회

풀이

재귀를 사용하여 풀 수 있습니다.

저는 Node라는 구조체 하나를 선언하여, left와 right 프로퍼티를 선언해주었습니다.
이는 자식노드의 왼쪽, 오른쪽을 표현합니다.

입력을 받아서 [String: Node] 의 딕셔너리 컬렉션에 값을 추가하였습니다.

모든 순회가 "A" 노드부터 시작됩니다.

preorder의 경우 루트 -> 왼쪽 -> 오른쪽 순으로 탐색을 진행합니다.
함수를 실행하면 현재 노드의 알파벳을 출력하고,
왼쪽 -> 오른쪽 자식노드에 대해서 "."이 아닐 때 까지 재귀로 파고들어가줍니다.

inorder와 postorder도 비슷하게 작성해줍시다.
inorder는 왼쪽, 출력, 오른쪽
postorder는 왼쪽, 오른쪽, 출력
순으로 작성해주면 됩니다.

소스코드

	struct Node {
	let left: String
	let right: String
	}
	let n = Int(readLine()!)!
	var tree: [String: Node] = [:]
	for _ in 0..<n {
	let input = readLine()!.split(separator: " ").map { String($0) }
	tree[input[0]] = Node(left: input[1], right: input[2])
	}
	func preorder(_ t: String) {
	if t == "." {
	return
	}
	print(t, terminator: "")
	preorder(tree[t]!.left)
	preorder(tree[t]!.right)
	}
	func inorder(_ t: String) {
	if t == "." {
	return
	}
	inorder(tree[t]!.left)
	print(t, terminator: "")
	inorder(tree[t]!.right)
	}
	func postorder(_ t: String) {
	if t == "."{
	return
	}
	postorder(tree[t]!.left)
	postorder(tree[t]!.right)
	print(t, terminator: "")
	}
	let orders = [preorder, inorder, postorder]
	orders.forEach {
	$0("A")
	print()
	}

view raw 트리 순회.swift hosted with ❤ by GitHub

후기

정답 비율도 높고, 실버 1의 난이도였지만 은근히 어려웠던 문제였습니다.
preorder만 구현한다면 나머지도 쉽게 구현할 수 있었던 문제였습니다.