반응형
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 >= size) return; 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 |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 11505번 - 구간 곱 구하기 (C++) (0) | 2022.07.09 |
|---|---|
| [ 백준 ] 2096번 - 내려가기 (C++) (0) | 2022.07.08 |
| [ 백준 ] 14502번 - 연구소 (C++) (0) | 2022.07.06 |
| [ 백준 ] 2357번 - 최솟값과 최댓값 (C++) (0) | 2022.07.05 |
| [ 백준 ] 2042번 - 구간 합 구하기 (C++) (0) | 2022.07.04 |