글 읽기 - 90%에서 틀렸습니다가 나옵니다.

yhd1411 6년 전 0

1. root가 1이 아닐수있다.

2. 부모노드가 자식보다 늦게나올수 있다.

를 고려하여

1번을 위해 자식의 부모를 저장하고 있으면서 탐색하여 root를 찾았습니다.

2번을 위해 벡터에 각 노드의 left,right를 저장했습니다.

맞았을거라고 생각했는데 90%에서 틀렸습니다가 나옵니다.

다음과 같이 소스를 작성했는데 어디가 틀렸는지 감이안오네요..

도와주세요!

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <queue>
#define INF 1234567890
using namespace std;

typedef pair<int, int> P;
vector<P> graph[10100]; //각 node의 left,right저장(pair로)
vector<int> arr[10100]; //각 level의 좌표를 저장할 vector
bool visited[10100];
int V;
int parent[101000];//root를 찾기위한 배열
int bread;
int _max_level;
int _root;

void find_root(int node)//root찾기
{
    while(parent[node])
    {
        node = parent[node];
    }
    _root= node;
}
void input() //graph배열에 각 node에 left,right저장
{
    int node, left, right;
    scanf("%d", &V);
    for(int i=0; i<V; i++)
    {
        scanf(" %d %d %d", &node, &left, &right);
        if(left!=-1)
            parent[left] = node;
        if(right!=-1)
            parent[right] = node;
        graph[node].push_back(make_pair(left, right));

    }
    find_root(node);
}

void bfs(int root, int level)
{
    if(_max_level < level)
        _max_level = level;
    visited[root] = true;
    if (graph[root].back().first == -1 && graph[root].back().second == -1) //leaf인 경우 bread증가후 종료
    {
        arr[level].push_back(++bread);
        return;
    }
    /*중위순회를 이용하여 너비 계산*/
    if (graph[root].back().first != -1 && !visited[graph[root].back().first])
        bfs(graph[root].back().first, level+1);

    arr[level].push_back(++bread);

    if (graph[root].back().second != -1&& !visited[graph[root].back().second])
        bfs(graph[root].back().second, level+1);
}
void output()
{
    int _max, _min, res_level=-1, res_bread=0;
    for(int i=1; i<=_max_level; i++) //level 1부터 _max_level까지 확인
    {
        _max=-INF;
        _min=INF;
        /*arr[i]에 들어있는 _max,_min을 찾고  너비를 구해 최대인경우 갱신*/
        for(vector<int>::iterator it=arr[i].begin(); it!=arr[i].end(); it++)
        {
            if(_max < (*it))
                _max = (*it);
            if(_min > (*it))
                _min = (*it);
        }
        if((_max-_min) > res_bread)
        {
            res_bread = _max-_min;
            res_level = i;
        }
    }
    printf("%d %d", res_level, res_bread+1);
}

int main()
{
    input();
    bfs(_root,1);
    output();
}

djm03178 6년 전 4

높은 %에서 틀렸다고 나온다면 좀 극단적인 케이스들을 의심해봐야 됩니다.

1 -1 -1

또는,

1 2 -1

2 3 -1

3 -1 -1

과 같이, 답이 루트 노드가 되어야 할 경우에 레벨이 -1로 출력됩니다. 즉, if((_max-_min) > res_bread) 에 한 번도 걸려들지 않을 경우가 고려되지 않았습니다.

yhd1411 6년 전 0

감사합니다. root가 답일때 핸들링해주니 바로 맞았네요!

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

문제

문제

출처

ICPC

90%에서 틀렸습니다가 나옵니다.

yhd1411 6년 전 0

djm03178 6년 전 4

yhd1411 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말