백준 2263 트리의 순회

출처: www.acmicpc.net/problem/2263

분류: 트리

---

접근방식

트리 순회 방법의 특성을 잘 이용해 해결했어야 하는 문제였습니다.

기억해야 할 특징은 다음과 같습니다.

1. post-order는 왼쪽 - 오른쪽 - 루트 순으로 탐색하므로 배열의 마지막은 루트노드가 됩니다.

2. in-order 는 root를 기준으로 왼쪽은 left, 오른쪽은 right 서브트리로 분리됩니다.

post-order를 통해 root 노드를 찾았다면, in-order의 시작부터 root 까지가 왼쪽, 오른쪽으로 분리되고,

이를 통해 왼쪽, 오른쪽에 몇 개의 노드가 존재하는지 알 수 있습니다.

다시 in-order는 왼쪽 - 오른쪽 - 루트가 순서대로 배치되어 있기 때문에 개수를 통해 in-order에서 어디까지가 왼쪽, 오른쪽인지 알 수 있게됩니다.

이러한 특성을 가지고 재귀적으로 탐색하면 원하는 결과를 얻을 수 있습니다.

 

예를 들어보겠습니다. 

다음과 같은 트리가 주어졌다면,

 

위에 말씀드린 특성을 이용해 아래와 같이 트리의 구조를 알아낼 수가 있습니다.

pre-order의 탐색 결과를 찾아야하므로 매번 root를 차곡차곡 담아주면 원하는 결과는 얻을 수 있게됩니다 :)

 

해결방법

import Foundation

let n = Int(readLine()!)!
let inOrderList = readLine()!.split(separator: " ").map { Int(String($0))! }
var postOrderList = readLine()!.split(separator: " ").map { Int(String($0))! }

var inOrderIndexTable = [Int: Int]()
inOrderList.enumerated().forEach {
  inOrderIndexTable[$0.element] = $0.offset
}

var preOrderListResult = [String]()

func makePreOrder(_ inStart: Int, _ inEnd: Int, _ postStart: Int, _ postEnd: Int) {
  guard inStart <= inEnd, postStart <= postEnd else { return }
  
  preOrderListResult.append("\(postOrderList[postEnd])")
  let rootIndexOfInOrder = inOrderIndexTable[postOrderList[postEnd]]!
  
  let leftPostCount = (rootIndexOfInOrder - inStart) - 1
  let leftPostEnd = postStart + leftPostCount
  
  // 왼쪽
  makePreOrder(inStart, rootIndexOfInOrder-1, postStart, leftPostEnd)
  // 오른쪽
  makePreOrder(rootIndexOfInOrder+1, inEnd, leftPostEnd+1, postEnd-1)
}

makePreOrder(0, inOrderList.count-1, 0, postOrderList.count-1)
print(preOrderListResult.joined(separator: " "))

 

배운점

처음에 감을 잡지 못해서 다른 분들의 블로그 풀이를 참고했다.

힌트를 얻고도 개수를 통해 다시 찾아나갈 수 있다는 걸 몰라서

루트로 왼쪽 오른쪽 나뉘는 건 알겠는데 그다음은 어떻게 하지? 하고 한참을 고민했다.

 

어렵다 어려워...

 

참고

꾸준함 - 구데타마 구데타마 님 블로그