2-R 무엇이 잘못되었을까요?

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

2-R

작성

예제는 다 통과하는데 제출하면 틀렸다고 나오네요..

bfs를 통해 풀었는데 뭐가 문제인지 잘 모르겠습니다.

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <iostream>
#include <vector>
#include <queue>

std::vector<int> tree[50];

void bfs(const int start, const int removeNumber)
{
    bool visited[50] = {false, };
    std::queue<int> que;
    que.push(start);
    visited[start] = true;
    
    int curr = 0;
    int count = 0;
    while(que.empty() == false)
    {
        curr = que.front();
        que.pop();
        for (int i = 0; i < tree[curr].size(); ++i)
        {
            if (!visited[tree[curr][i]] && tree[curr][i] != removeNumber)
            {
                if (tree[tree[curr][i]].size() == 0)
                {
                    count += 1;
                    continue;
                }
                que.push(tree[curr][i]);
                visited[tree[curr][i]] = true;
            }    
        }
        
    }
    
    std::cout << count << "\n";
    
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    
    int N, temp, removeNumber;
    
    std::cin >> N;
    
    for(int i = 0; i < N; ++i)
    {
        std::cin >> temp;
        if (temp == -1)
        {
            continue;
        }
        
        tree[temp].push_back(i);
    }
    
    std::cin >> removeNumber;
    if (removeNumber == 0)
    {
        std::cout << 0 << "\n";
        return 0;
    }

    bfs(0, removeNumber);

    return 0;
}

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 HELLO님 ㅎㅎ

루트가 지워지는 경우의 수, 리프노드 관련 카운팅 부분 로직에 관해 코드가 수정이되어야 합니다.

    if (removeNumber == 0)

ex) 이런 부분 등.

제가 한번 다듬어봤는데요. ㅎㅎ 참고부탁드립니다.

#include <iostream>
#include <vector>
#include <queue>

std::vector<int> tree[50];

void bfs(const int start, const int removeNumber)
{
    bool visited[50] = {false, };
    std::queue<int> que;
    que.push(start);
    visited[start] = true;

    int curr = 0;
    int count = 0;
    while(!que.empty())
    {
        curr = que.front();
        que.pop();
        bool isLeaf = true;
        for (int i = 0; i < tree[curr].size(); ++i)
        {
            if (tree[curr][i] != removeNumber && !visited[tree[curr][i]])
            {
                isLeaf = false;
                que.push(tree[curr][i]);
                visited[tree[curr][i]] = true;
            }
        }
        if (isLeaf)
        {
            count += 1;
        }
    }

    std::cout << count << "\n";
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int N, temp, removeNumber, root = -1;

    std::cin >> N;

    for(int i = 0; i < N; ++i)
    {
        std::cin >> temp;
        if (temp == -1)
        {
            root = i;
        }
        else
        {
            tree[temp].push_back(i);
        }
    }

    std::cin >> removeNumber;

    if (removeNumber == root)
    {
        std::cout << 0 << "\n";
        return 0;
    }

    bfs(root, removeNumber);

    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

HELLO

질문자

답변 감사드립니다.

잘 작동되는 것을 확인했는데, bfs 내에서 isLeaf 변수를 선언해서 체크하는 것과 기존에 제가 size를 체크하는 방법과 어떤 차이가 있는 걸까요..?
count를 증가시킬 때 제가 하는 방법으로 증가시킬 경우에는 통과되지 않네요...

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

2-R 무엇이 잘못되었을까요?