[백준]2263. 트리의 순회
백준의 2263. 트리의 순회 문제에 대한 정리이다.
문제 설명
1~N 까지 번호가 매겨져 있는 N개의 정점을 가지는 이진 트리가 있다.
이 트리의 *In-Order와 *Post-Order가 주어질 때, *Pre-Order를 구하는 프로그램을 작성하면 된다.
- In-Order: 트리를 ‘①왼쪽 노드 - ②루트 노드 - ③오른쪽 노드’ 순서대로 탐색하는 것
- Post-Order: 트리를 ‘①왼쪽 노드 - ②오른쪽 노드 - ③루트 노드’ 순서대로 탐색하는 것
- Pre-Order: 트리를 ‘①루트 노드 - ②왼쪽 노드 - ③오른쪽 노드’ 순서대로 탐색하는 것
출처: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
원래 생각한 아이디어
이 문제를 풀기 이전에, 유사한 문제를 푼 경험이 있어서 해당 문제에서 사용했던 아이디어를 차용하려고 했다.
5639. 이진 검색 트리 라는 문제인데, 해당 문제는 전위 순회(Pre-Order)한 결과가 주어지면 해당 트리를 후위 순회(Post-Order)한 결과를 반환해야 하는 문제이다.
이 문제에서 주어지는 ‘현재 노드의 왼쪽 서브트리의 모든 노드 키 < 현재 노드의 키 < 현재 노드의 오른쪽 서브트리의 모든 노드 키’ 라는 조건을 활용하는 문제였다.
먼저 전위 순회한 값들을 배열에 저장한 뒤, ‘start - end’ 범위 내에서 맨 왼쪽의 키 값을 뽑아낸 뒤 그 값보다 작은값을 만날 때 까지, 큰 값을 만날 때 까지 탐색 한다.
그리고 ‘start+1 ~ 큰 값을 만난 위치’, ‘큰 값을 만난 위치 ~ end’ 두 가지 서브 트리로 쪼갠 뒤 분할 탐색을 하는 것을 반복하는 식으로 해결하면 되는 문제였다.
‘트리의 순회’문제에서 Post-Order가 주어지기 때문에, 비슷한 방식으로 풀 수 있다고 생각했다.
- 먼저 ‘start - end’ 범위 내 맨 오른쪽 값(= 루트 값)을 뽑아낸 뒤, 해당 값 바로 왼쪽 값을 찾아낸다. 그 값이 오른쪽 서브 트리의 루트 노드 값이다.
- 오른쪽 서브트리 루트 값 보다 낮은 값이 나올 때 까지 start 쪽으로(= 왼쪽으로) 탐색한다.
- 그리고 낮은 값을 찾으면 해당 값이 왼쪽 서브트리 루트 값이다.
- ‘start ~ 왼쪽 서브트리 루트 값 idx’, ‘왼쪽 서브트리 루트 값 idx+1, end-1’ 으로 분할 탐색을 하면? 문제가 풀릴 줄 알았다.
발생한 문제
하지만 순탄하게 풀리지 않았는데, 바로 이 문제에는 ‘이진 검색 트리’ 문제 처럼 조건이 주어지는게 아니기 때문에 해당 공식이 성립하지 않는다는 것이었다.
실제로 코드를 제출 했을때도 오답으로 나왔고, 백준에 다른 유저분들이 올려주신 반례들을 보니 저 조건이 성립하지 않고 번호가 무작위로 매겨져 있었다.
특히, 한 쪽으로 편향된 케이스의 경우 Post-Order는 같지만 In-Order는 달라 이 방법이 아님을 알게 되었다.
답안 아이디어
그래서 이 문제를 거의 이틀 정도 계속 붙잡고 풀어 본 결과, In-Order와 Post-Order에서 규칙을 발견할 수 있었다.
- Post-Order에서 범위 내 맨 오른쪽 값은 root다.
- 해당 root 값을 In-Order에서 찾아내면, 그 위치를 기준 좌/우로 서브트리가 나뉜다.
- In-Order에서 root의 바로 오른쪽 원소 값의 Post-Order 상 idx를 찾아내면, Post-Order에서 [start ~ idx-1], [idx ~ end-1]로 서브트리를 탐색할 수 있다.
이를 그림으로 나타내면 다음과 같다.
다만, 왼쪽이나, 오른쪽에 서브트리가 없을 수 있으므로 탐색 범위 체크가 필요하다.
해당 방법대로 계속 범위를 줄여나가며 분할 정복하며 만나는 root들을 StringBuffer에 저장했다가 탐색이 끝나고 출력해주면 문제를 해결할 수 있다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 주어지는 In-Order, Post-Order의 순서는 다음과 같음
// ---------------------------------------
// In-Order -> 왼쪽 - 루트 - 오른쪽 순서대로 탐색
// Post-Order -> 왼쪽 - 오른쪽 - 루트 순서대로 탐색
// ---------------------------------------
// 답으로 출력해야 하는 Pre-Order의 순서는 다음과 같음
// ---------------------------------------
// Pre-Order -> 루트 - 왼쪽 - 오른쪽 순서대로 탐색
// ---------------------------------------
// 답 아이디어
// 1. Post-Order 순서에서는 현재 서브트리의 맨 오른쪽의 원소가 Root임
// 2. In-Order 순서에서는 현재 서브트리의 Root 노드 번호 를 기준으로 왼쪽, 오른쪽 서브트리가 나뉨.
// 3. 따라서, Post-Order에서 맨 오른쪽 요소를 뽑아내 Root 노드 번호를 찾고,
// 해당 노드 번호의 In-Order에서의 idx를 알아내면, 해당 idx 좌, 우로 서브트리를 탐색할 수 있다.
// 또한, root의 In-Order idx의 바로 오른쪽 원소 값의 Post-Order 상 idx를 찾아내면,
// Post-Order에서 [start ~ idx-1], [idx ~ end-1] 로 서브트리를 탐색할 수 있다.
// 이러한 방식으로 루트, 좌/우 서브트리를 계속 탐색하면서 발견하는 원소값을 StringBuffer에 누적시켜
// 탐색이 다 끝난 뒤 출력하면 Pre-Order 순서대로 출력할 수 있다.
public class Main {
static int inOrder[][], postOrder[][], N;
static StringBuffer sb;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuffer();
N = Integer.parseInt(br.readLine());
inOrder = new int[2][N+1];
postOrder = new int[2][N+1];
String strArr[] = br.readLine().split(" ");
// inOrder[0][] -> index가 inOrder[1]에서 몇 번째 위치인지
// inOrder[1][] -> 입력 순서대로 받은 inOrder
for(int i=0; i<N; i++) {
inOrder[1][i] = Integer.parseInt(strArr[i]);
inOrder[0][inOrder[1][i]] = i;
}
strArr = br.readLine().split(" ");
// postOrder[0][] -> index가 postOrder[1]에서 몇 번째 위치인지
// postOrder[1][] -> 입력 순서대로 받은 postOrder
for(int i=0; i<N; i++) {
postOrder[1][i] = Integer.parseInt(strArr[i]);
postOrder[0][postOrder[1][i]] = i;
}
// preOrder 탐색 시작
search(0, N-1, 0, N-1);
System.out.println(sb.toString());
}
// postOrder 상에서의 탐색 시작, 종료 범위 start, end
// inOrder 상에서의 탐색 시작, 종료 범위 s, e
public static void search(int start, int end, int s, int e) {
// 탐색 범위값이 엇나갔으면 탐색 종료
if(start > end || s > e) return;
// root 노드 출력에 추가
int root = postOrder[1][end];
sb.append(root);
sb.append(" ");
// 하위 노드가 없는 상태, 즉 더 탐색할 수 없는 경우 탐색 종료
if(start == end) return;
// root 노드의 inOrder 상 idx 추출
int centeridx = inOrder[0][root];
// 좌/우 서브트리를 구분하는 임계점 저장할 변수
int threshHold = end-1;
// inOrder에서 root 노드 기준 오른쪽이 탐색 범위를 벗어나지 않는 경우
// 즉 오른쪽 서브노드 탐색 가능한 경우
if(centeridx+1 <= e) {
// inOrder에서 root 노드 바로 오른쪽 노드 값 추출
int rightLast = inOrder[1][centeridx+1];
// 해당 값의 postOrder 상의 idx 추출
// 이 값이 postOrder상에서 왼쪽/오른쪽 서브트리 나누는 임계값
threshHold = postOrder[0][rightLast];
// inOrder에서 root 노드 기준 왼쪽이 탐색 범위를 벗어나지 않는 경우
// 즉 왼쪽 서브노드 탐색이 가능한 경우
if(centeridx-1 >= s) {
// 임계점 기준으로 왼쪽 먼저 탐색한 뒤, 오른쪽 탐색
search(start, threshHold-1, s, centeridx-1);
search(threshHold, end-1, centeridx+1, e);
} else {
// 오른쪽은 탐색 가능하지만 왼쪽은 탐색할 수 없는 경우 이므로
// 오른쪽으로만 탐색
search(start, end-1, centeridx+1, e);
}
} else {
// 오른쪽 탐색 불가능 하므로 왼쪽으로 탐색
search(start, threshHold, s, centeridx-1);
}
}
}
결론
처음 시작을 잘못된 방향으로 생각을 해서 거기에 옳메인게 너무 컸던것 같다.
앞으로는 비슷한 유형의 문제라도 다른 방법으로 먼저 생각해보는 방향으로 문제를 풀어야 겠다.
