글 읽기 - 79%에서 자꾸 틀립니다.

suno 3년 전 0

안녕하세요.

이 문제를 (리프 노드 수) = (처음 리프 노드) - (제거된 리프 노드 수) 에다가 추가로,

삭제할 노드의 부모가 자식이 하나로 유일할 경우 자식이 삭제되면 리프 노드가 추가되는 경우에만 리프 노드를 하나 추가해 주었습니다.

새롭게 리프 노드가 생성되는 경우는 이 하나밖에 없다고 생각했는데, 다른 경우가 있는 건가요?

질문글에 79%에서 오류 내는 반례들은 시도해 봤는데 정상적으로 작동했습니다.

원인을 알고 싶습니다ㅜㅜ

#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <string.h>
#include <string>

#define MAX 55

using namespace std;

vector<vector<int>> children;
vector<int> parentVec;
int leaf_num = 0;

void deleteNode(int root) //해당 노드를 root로 가지는 subtree의 리프 노드 수만큼 leaf_node--
{
    if (children[root].size() == 0) //지울 노드가 리프 노드면 leaf_num--;
    {
        leaf_num--;
        return;
    }
    for (auto child : children[root]) //리프 노드가 아니면 자식들 삭제
        deleteNode(child);
}

int main()
{
    ////////////////////input////////////////////
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n, parent, root = -1, toDelete;
    cin >> n;
    children.resize(n);
    parentVec.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> parent;
        parentVec.push_back(parent);
        if (parent != -1)
            children[parent].push_back(i);
        else
            root = i;
    }
    assert(root != -1);
    cin >> toDelete;

    if (toDelete == root) //root를 지우는 경우
    {
        cout << 0;
        return 0;
    }

    for (auto childrenVector : children)
    {
        if (childrenVector.size() == 0)
            leaf_num++;
    }
    deleteNode(toDelete);
    if (children[parentVec[toDelete]].size() == 1)
        leaf_num++;

    ////////////////////output///////////////////
    cout << leaf_num;

    return 0;
}

/*legacy



*/

djm03178 3년 전 3

반례입니다.

https://ideone.com/lBAUFg

35번째 줄에서 크기를 이미 n으로 늘렸는데 39번째 줄에서 push_back을 또 하고 있어서, 실제로는 parent[n]부터 parent[n+n-1]에 부모 정보들이 들어가게 됩니다.

suno 3년 전 0

아 resize하면 뒤에서부터 추가되는 거였군요! 멍청하게 reserve랑 헷갈렸나봅니다ㅠ 중요한 것 배워 갑니다..

답변 감사합니다!! 덕분에 해결됐습니다.

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

문제

문제

출처

ICPC

79%에서 자꾸 틀립니다.

suno 3년 전 0

djm03178 3년 전 3

suno 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말