반응형

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

 

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

입력받은 수의 부모 노드를 기준으로 왼쪽에 있는 노드와 오른쪽에 있는 노드를 구분하여 왼쪽 노드부터 출력해주면 됩니다.

 

현재 노드에서 값이 커지는 부분이 오른쪽 노드이므로 for문을 돌려서 현재 노드 +1 ~ 값이 커지는 노드 직전까지 왼쪽 노드이고, 값이 커지는 노드 ~ 그래프 사이즈까지 오른쪽 노드입니다. 이를 이용하여 문제를 풀어주면 됩니다.

 

[ 소스 코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
 
using namespace std;
 
int arr[10000];
int i;
 
void dfs(int node, int size)
{
    if (node >= sizereturn;
 
    for (i = node + 1; i < size; i++) {
        if (arr[node] < arr[i]) break;
    }
 
    dfs(node + 1, i);    //왼쪽
    dfs(i, size);        //오른쪽
    printf("%d\n", arr[node]);
 
    return;
}
 
int main()
{
    int idx = 0;
 
    while (scanf("%d"&arr[idx]) != EOF)
    {
        idx++;
    }
 
    dfs(0, idx);
}
cs
반응형

+ Recent posts