글 읽기 - BFS와 inorder traversal을 이용했는데 어디가 틀렸는지 모르겠어요

hyeonsuns 5년 전 0

문제는 DFS로 이용하는 것이라 되있지만

BFS와 inorder traversal로 구했습니다.

어디가 잘못되었는지 모르겠네요.. 답은 잘나오는데...

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n;
vector<int> tree[10001];
int check[10001];
int column[10001];
int colIdx = 1;

int area[10001];

void inorderTraversal(int node) {

    if(node == -1) return;

    int v1 = tree[node][0];
    int v2 = tree[node][1];
    inorderTraversal(v1);
    column[colIdx++] = node;
    inorderTraversal(v2);
}

void BFS(int node) {

    check[node] = 1;
    queue<int> q;
    q.push(node);

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int i = 0;i<tree[cur].size();i++) {
            int next = tree[cur][i];

            if(!check[next] && next != -1) {
                check[next] = check[cur] + 1;
                q.push(next);
            }
        }
    }
}

int main(void)
{


    scanf("%d", &n);

    for(int i = 0;i<n;i++) {
        int u, v1, v2;
        scanf("%d %d %d", &u, &v1, &v2);

        tree[u].push_back(v1);
        tree[u].push_back(v2);
    }

    BFS(1); // 각각의 레벨 구성


    inorderTraversal(1);    // 각각의 열 번호 구성

    vector<int> rowCol[10001];

    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=n;j++) {
            if(column[j] == i)
                rowCol[check[i]].emplace_back(j);       // 레벨별 열 삽입
        }
    }

    int maxLevel = 0;       // 레벨 수 계산
    for(int i = 1;i<=n;i++)
        if(maxLevel < check[i])
            maxLevel = check[i];

    int Min = 10001, Max = 0;
    for(int i = 1;i<=maxLevel;i++) {

        for(int j = 0;j<rowCol[i].size();j++) {
            if(rowCol[i][j] < Min) Min = rowCol[i][j];
            if(rowCol[i][j] > Max) Max = rowCol[i][j];
        }
        area[i] = Max - Min + 1;           // 너비 계슨
        Min = 10001; Max = 0;
    }

    long long resultLevel, resultArea = 0;
    for(int i = 1;i<=maxLevel;i++) {
        if(area[i] > resultArea) {
            resultArea = area[i];
            resultLevel = i;
        }
    }

    printf("%lld %lld\n", resultLevel, resultArea);

    return 0;
}

seico75 5년 전 2

루트를 1이라고 가정할 수 있나요? 문제에는 그런 이야기가 없는 것 같습니다.

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

문제

문제

출처

ICPC

BFS와 inorder traversal을 이용했는데 어디가 틀렸는지 모르겠어요

hyeonsuns 5년 전 0

seico75 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말