글 읽기 - 코드의 반례나 오류를 찾지 못하겠습니다.

ktb5057 1년 전 0

졸면서 하느라 변수명이 고쳐지지 않은 점이 있지만,

Tree 구조체의 level 변수는 루트 노드를 찾기 위한 장치이고,

전역 변수인 level과 main이외의 함수에서 사용된 level은 노드의 깊이를 나타내는 값입니다.

문제의 예시나 질문글에서 다른 분들이 공유해주시는 예시를 다 통과하지만 제출시 항상 '틀렸습니다'가 결과로 나오네요.

루트를 확인하는 것과 같은 너비의 깊이가 있을시 가장 낮은 깊이를 출력하는 것도 해결했다고 생각하는데

어디서 틀린 걸까요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

struct Tree{
    Tree *right, *left;
    int value = -1;
    int level = -1;
};

void in_order(Tree *node, int deep);
void search_result();

const int MAX = 10000;
struct Tree tree_arr[MAX+1];
vector<vector<int>> box(MAX+1);
int n;
int cnt = 0;
int level = 0;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int p, x, y;
    int root = -1;
    Tree null_node;
    null_node.value = -1;
    null_node.level = -1;
    
    for(int i=0; i < n; i++){
        cin >> p >> x >> y;
        tree_arr[p].value = p;
        if(tree_arr[p].level == -1){
            tree_arr[p].level = 1;
            root = p;
        }

        if(x != -1){
            tree_arr[x].value = x;
            tree_arr[x].level = tree_arr[p].level + 1;
            tree_arr[p].left = &tree_arr[x];
        }else{
            tree_arr[p].left = &null_node;
        }

        if(y != -1){
            tree_arr[y].value = y;
            tree_arr[y].level = tree_arr[p].level + 1;
            tree_arr[p].right = &tree_arr[y];
        }else{
            tree_arr[p].right = &null_node;
        }
    }
    in_order(&tree_arr[root], 1);

    search_result();
}

void in_order(Tree *node, int deep){
    if(node->value == -1) return;
    if(deep > level) level = deep;
    in_order(node->left, deep+1);
    box[deep].push_back(cnt++);
    in_order(node->right, deep+1);
}

void search_result(){
    int r_level = 0;
    int width_l = 0;
    for(int i=1; i <= level; i++){
        if(box[i].back() - box[i].front() + 1 > width_l){
            width_l = box[i].back() - box[i].front() + 1;
            r_level = i;
        }
    }

    cout << r_level << ' ' << width_l << endl;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

코드의 반례나 오류를 찾지 못하겠습니다.

ktb5057 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말