인프런 커뮤니티 질문&답변

김현우님의 프로필 이미지
김현우

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-N

3-N 질문있습니다.

해결된 질문

작성

·

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

감사합니다.

강사 큰돌 올림.


김현우님의 프로필 이미지
김현우

작성한 질문수

질문하기