[백준 4256][C++] 트리 (Gold 5)

[문제보기]

 4256. 트리

4256번: 트리

 

[풀이과정]

이 문제는 풀기에는 너무 어려웠다. 그리고 블로그를 참고를 했지만, 자세한 설명은 없고 그냥 재귀로 하면 된다고 해서

이해하는데 조금 힘들었다. 하지만 하나하나 손으로 그려가면서 코드를 집어가면서 온전히 내 것으로 만들 수 있었다. 

 

1. 전위 순회에서 첫번째 노드는 루트 노드

2. 중위 순회에서 루트 기준 앞쪽 노드는 왼쪽 서브 트리, 뒷쪽은 오른쪽 서브트리

라는 것을 생각하면서 문제를 풀어보면 된다.

 

 

예제 1번의 두번째 테스트 케이스를 예를 들면서 코드를 설명하겠다.

8

3 6 5 4 8 7 1 2

5 6 8 4 3 1 2 7

 

이 케이스의 트리 모양은 이런 모양이 형성이 되어 있다. 이 모양을 기억!!

 

2번째 입력값(중위 순회)을 받을 때 map 함수를 사용하여 각 노드 번호가 몇번 째에 나왔는지 저장을 해준다. 

예를 들어 2번째 입력에서 5를 받으면 map[5] = 1 (5번은 첫번 째로 등장)

6을 입력 받으면 map[6] = 2 (6번은 두번 째로 등장) 

3을 입력 받으면 map[3] = 5 (3번은 다섯 번째로 등장) 식이 된다.

 

그리고 go() 함수를 사용하여 재귀를 통해 후위 순회를 출력해주면 되는데,

go() 함수의  파라미터로는 pre_start, pre_end, in_start, in_end 4가지를 주어준다.

 

1번째 재귀

go(1, 8, 1, 8)

root : 3, pos: 5가 되고, 3번을 기준으로 왼쪽 서브트리, 오른쪽 서브트리로 나눠서 재귀를 사용한다.

그렇기 때문에 밑의 go() 함수들은

go(2, 5, 1, 4)

go(6, 8, 5, 8)

두개로 나눠지게 된다.

 

2번째 재귀

go(2, 5, 1, 4)

3번을 기준으로 왼쪽 서브트리를 가지고 왔다.

pre[] 배열 중에 {6, 5, 4, 8}을 가져오게 되고 (pre_start(2), pre_end(5))

mp[] 배열 중에 {5, 6, 8, 4}를 가져왔다(in_start(1), in_end(4))

이제 여기서 pre[]의 맨 앞에 있는 번호가 루트 노드가 되고(root = 6)

pos는 2가 된다. 

그렇기 때문에 6번 노드를 기준으로 왼쪽 서브트리, 오른쪽 서브트리를 나뉘게 되어

go(3, 3, 1, 1)

go(4, 5, 3, 4)

두 개로 나눠지게 된다.

 

3번째 재귀

go(3, 3, 1, 1)

6번 노드를 기준으로 왼쪽 서브 트리를 가지고 왔다.

root = 5, pos = 1

그리고 밑의 두개의 go() 함수를 통해 재귀를 들어가지만 5번 노드의 자식 노드들이 없기 때문에 바로 return이 일어나고

첫 번째로 5가 후위순회에 찍히게 된다.

 

잘 이해가 안됀다면 손으로 그려보면서 하는 것을 추천

이건 필자가 손으로 하나하나 해본 이미지이다.

 

[소스코드]

#include <iostream>
#include <map>
#include <cstring>
using namespace std;

int t, n;
int pre[1010];
int in[1010];
map<int, int> mp;
 
void go(int pre_start, int pre_end, int in_start, int in_end) {
 
    if (pre_start > pre_end || in_start > in_end) return;
 
    int root = pre[pre_start];
    int pos = mp[pre[pre_start]];
 
    go(pre_start + 1, pre_start + (pos - in_start), in_start, pos - 1);
    go(pre_start + (pos - in_start) + 1, pre_end, pos + 1, in_end);
    cout << root << " ";
}

int main() {
    cin >> t;
    while (t--) {
        memset(pre, 0, sizeof(pre));
        mp.clear();
        cin >> n;

        for (int i = 1; i <= n; i++) 
            cin >> pre[i];

        for (int i = 1; i <= n; i++) {
            int x; 
            cin >> x;
            in[i] = x;
            mp[x] = i;
        }

        go(1, n, 1, n); 
        cout << "\n";
    }
}

 

[참고]

sejinik.tistory.com/15