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

http://boj.kr/2bf60dd2888045f2a43e2154e2fe0bd5

반례도 해결하도록 고쳐보았는데 또 오답이네요 ㅠ 무엇이 문제일까요

잘 짜셨네요 은정님 ㅎㅎ

하지만 b[i]를 이용한 부분이 좀 부족하셨습니다.

        for (int i = 0; i < n; i++)
        {
            if(b[i] == false) continue;
            if (adj[i].size() == 0) ret++; 
            else{
                bool flag = 1;
                for(int j : adj[i]){
                    if(b[j] == true)flag = 0;
                }
                if(flag)ret++;
            }
        }

지금 보시는 것 처럼

1. 지운정점-> 탐색x하게

2. 이 지운 정점을 자식으로 가졌다? 모두 지워져서 size == 0일 때만 카운팅 하게 하시면 됩니다.

나머지 부분은 정말 잘 짜셨습니다. 굿굿ㅎㅎ

고친 전체 코드.

#include <bits/stdc++.h>
using namespace std;

// 인접 리스트를 만드는데 양방향이 아니라, 자기 자식들만 담아
// 지우고 남은 것 인접리스트가 0인 것들과 + 루트노드 1개?

int n, a[52], k, ret;
vector<int> adj[52];

bool b[52];

void cut(int node)
{
    b[node] = false;

    for (int s : adj[node])
    {
        cut(s);
    }
}

int main()
{

    // 입력 받기
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] != -1)
            adj[a[i]].push_back(i);
        b[i] = true;
    }

    cin >> k;

    if (a[k] == -1){
        ret = 0;
    }     
    // 노드 삭제
    else
    {
        cut(k);

        for (int i = 0; i < n; i++)
        {
            if(b[i] == false) continue;
            if (adj[i].size() == 0) ret++; 
            else{
                bool flag = 1;
                for(int j : adj[i]){
                    if(b[j] == true)flag = 0;
                }
                if(flag)ret++;
            }
        }
    }

    cout << ret;
}

// 테스트 케이스 통과  but 틀림..

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.