[BOJ][5639번] - 이진 검색 트리 (순회 바꾸기)

안녕하세요 Dibrary입니다.

이번에는 이진검색트리에서 '전위순회'한 값 순서가 주어질 때, 이 값을 '후위순회'한 값 순서로 바꾸는 문제입니다.

재귀를 떠올리지 못해서 도대체 어떻게 해야 하나 아주 알머리를 고민했던 문제입니다...

문제는 아래와 같습니다.

 

제일 먼저 든 생각은 '전위 순회는 어떻게 하는 거였더라~?' 입니다. 

전위순회는 루트 먼저 가고 좌, 우 를 방문합니다.

 

이게 무슨말일까요? 위 문제에서 주어진 예시를 통해 확인해보겠습니다.

먼저 이렇게 3개만 놓고 볼 때, 루트는 50이고, 왼쪽을 먼저 간다고 했으니 30을 방문하겠네요.

다음으로 30을 루트로 놓고 볼 때, 왼쪽 24를 먼저 방문하겠네요. 

24를 루트로 놓고 볼 때, 5를 방문하고, 5는 더이상 자식노드가 없죠. 그럴 때 오른쪽을 방문합니다. 

그럼 여기까지 순서는 50-30-24-5-28 이렇게 되겠네요. 그리고 루트 24를 기준으로 한 노드는 모두 방문했으므로 다시 위로 올라가면서 '오른쪽'에 값들을 읽어나가면 됩니다.

그래서 50의 왼쪽은 30-24-5-28-45를 방문합니다. 

과연 맞는지? 확인해보죠. 네 50을 루트로 해서 45까지 순서가 일치하네요!. 이렇게 찾아가는 것이 '전위순회'입니다.

 

---

그러면 전위순회로 나온 값을 통해 우리는 여기서 규칙을 하나 알 수 있습니다.

1. 반드시 시작점은 전체 트리의 루트다. (루트먼저 방문해야 하기 때문이죠)
2. 루트보다 작은값을 무조건 다 방문한다. 즉, 루트 왼쪽을 모두 방문해야 오른쪽을 읽어들어간다.
3. 루트는 루트의 왼쪽이 다시 루트로 되면서 깊게 들어가고 오른쪽을 읽어들어오며 나온다.

 

---

코드는 아래와 같습니다.

재귀 깊이를 해제하고자 setrecursionlimit값을 재설정 해 줬습니다.

중간에 index 값을 확인해보고자 mid, first, end 출력 코드를 넣었습니다.

 

 

코드가 어떻게 동작하는지 보겠습니다. 문제에서 주어진 예시를 넣게 되면,

first = 0, mid = 6, end = 8
first = 1, mid = 5, end = 5
first = 2, mid = 4, end = 4
first = 3, mid = 4, end = 3

그리고 5가 제일 먼저 나옵니다.

first = 0일 때는 50을 기준으로 큰 값과 작은 값이 있는지 확인한 것입니다. 제일먼저 50보다 큰 값으로 나오는 98의 인덱스가 0부터 셀 때 6인 것을 알 수 있죠. 

그 다음에 first = 1일 때(재귀 코드로 다시 들어간 것입니다.) 30을 기준으로 30보다 큰 값으로 먼저 나오는 45의 인덱스가 5인 것을 알 수 있죠.

그 다음에 first = 2일 때 24를 기준으로 24보다 큰 값으로 먼저 나오는 28의 인덱스가 4인 것을 알 수 있습니다.

그리고, first = 3일 때는 5를 기준으로 확인하는데 5보다 큰 값이 없죠? 그래서 5가 제일 먼저 재귀 코드 내에서 print문으로 도착합니다. 출력이 제일 먼저 이뤄졌고,

그 다음에 다시 first = 2단으로 갑니다.(재귀로 들어갔으니까요). 그러면 아까 5랑은 다르게 24보다 큰 값이 있었죠? 해당 값이 먼저 나오고 루트 값이 나오게 됩니다. 즉 여기까지 출력은 5-28-24가 나오겠네요

그 다음에 first = 1로 갑니다. 여기서도 역시 큰 값인 45가 있었으므로 5-28-24-45-30 이런 식으로 나올 것입니다.

그리고 first = 0으로 갔는데, 50보다 큰 값이 3개나 있죠? 해당 값으로 재귀가 다시 들어갑니다. 

 

따라서 결과가 5-28-24-45-30-60-52-98-50 이렇게 나오게 됩니다.

 

---

제가 생각하기에 이 코드는 '생각'은 꽤 해볼 수 있지만, 초심자가 풀어내기는 아주 어렵지 않나 싶습니다. 재귀의 달인급이 아니고서는;; (전 아니네요)

그럼에도 이렇게 한 번 확인하고 제대로 분석하고 나니 '재귀'와 '순회' 2개에 대해서 좀 더 잘 알게 된 거 같습니다.