3-N 질문있습니다.

작성한 질문수 22

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.