반응형
https://www.acmicpc.net/problem/22856
22856번: 트리 순회
노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다.
www.acmicpc.net
[ 문제풀이 ]
1. 중위 순회를 수행하여 끝 노드를 찾아 저장합니다.
2. flag를 false로 초기화하고, 1번 노드부터 dfs를 돌아 flag가 false인 동안 노드를 옮기면 ans++를 해줍니다.
3. 트리를 순회 중 끝 노드를 만나면 flag를 true로 바꾸어줍니다.
4. ans를 출력합니다.
[ 소스코드 ]
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include<iostream> #include<vector> using namespace std; int N; vector<int> list[100001]; int ans; int last; bool flag = false; int checkEnd(int cur) { int end; int left = list[cur][0]; int right = list[cur][1]; if (left != -1) end = checkEnd(left); end = cur; if (right != -1) end = checkEnd(right); return end; } void dfs(int cur) { int left = list[cur][0]; int right = list[cur][1]; if (left != -1) { dfs(left); ans++; } if (right != -1) { dfs(right); ans++; } if (last == cur) flag = true; if (flag) return; ans++; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i < N; i++) { int a, b, c; cin >> a >> b >> c; list[a].push_back(b); list[a].push_back(c); } last = checkEnd(1); dfs(1); cout << ans; } | cs |
. 입력받은 부모 노드를 기준으로 vector<int> list[ 50 ] 배열에 그래프를 저장합니다.
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 15243번 - Tiling (C++) (0) | 2023.07.18 |
|---|---|
| [ 백준 ] 4811번 - 알약 (C++) (0) | 2023.07.17 |
| [ 백준 ] 7453번 - 합이 0인 네 정수 (C++) (0) | 2023.07.15 |
| [ 백준 ] 2295번 - 세 수의 합 (C++) (0) | 2023.07.14 |
| [ 백준 ] 1477번 - 휴게소 세우기 (C++) (0) | 2023.07.13 |