해결된 질문
작성
·
48
0
http://boj.kr/907e9f4775da48d8bb4c13e5d16d0c21
결국 그럼
중앙이 루트
좌우 나눠서 그곳의 중앙이 또 parent
이걸 무한히 반복한다고 생각햇고
BFS를 레벨별로 묶어서 처음에는 root를
그다음에는 root에 연결된 자식을
그 다음에는 그것에 연결된 자식들을 출력하는 방식으로 풀었습니다.
하지만 출력 초과가 나와서 어떤 문제가 있는지 궁금합니다.
답변 1
0
안녕하세요 현우님 ㅎㅎ
하지만 출력 초과가 나와서 어떤 문제가 있는지 궁금합니다.
>>
BFS로 풀려고 하시는 의도는 알겠지만 a-- , now - a또는 + a 부분으로 하게 되면 트리를 올바르게 출력하지 못합니다.
반례는 다음과 같습니다.
4
8 4 10 2 6 9 12 1 3 5 7 11 13 14 15
// 현우님 답
1
4 14
12 3
10 7 6 13
9 1 14 4 1 5 0
2 1 9 5 11 0 2 9 5 1 11 14
10 6 12 3 6 12 3 7 7 13 15 10 6 6 12 3 7 12 3 7 13 13 15
// 정답
1
2 11
4 9 5 14
8 10 6 12 3 7 13 15
제가 한번 BFS로 짜봤는데요.
이런걸 의도하신게 아닌가요? 참고부탁드립니다.
#include <bits/stdc++.h>
using namespace std;
int K;
vector<int> arr;
vector<vector<int>> levels; // 제 생각에는 b라는 배열이 levels 배열을 의미하는 것 같은데 이렇게 하는게 좋습니다.
void bfs(int start, int end) {
queue<pair<int, pair<int, int>>> q; // {레벨, {start, end}} 입니다.
q.push({0, {start, end}});
while (!q.empty()) {
int level = q.front().first;
int s = q.front().second.first;
int e = q.front().second.second;
q.pop();
int mid = (s + e) / 2;
levels[level].push_back(arr[mid]);
if (s < mid) {
q.push({level + 1, {s, mid - 1}});
}
if (mid < e) {
q.push({level + 1, {mid + 1, e}});
}
}
}
int main() {
cin >> K;
int n = (1 << K) - 1; // 2^K - 1 go() 함수보다는 이게 더 깔끔합니다.
arr.resize(n);
levels.resize(K);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
bfs(0, n - 1);
for (int i = 0; i < K; i++) {
for (int j = 0; j < levels[i].size(); j++) {
cout << levels[i][j] << " ";
}
cout<<"\n";
}
return 0;
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.