inflearn logo
강의

講義

知識共有

10週間完成 C++ コーディングテスト | アルゴリズムコーディングテスト

2-R

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

241

HELLO

投稿した質問数 13

0

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

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

1

kundol

안녕하세요 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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

 

0

HELLO

답변 감사드립니다.

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

코딩살구클럽 가입부탁드립니다

0

27

2

코딩살구클럽 가입 요청 확인부탁드립니다

0

30

2

5-S 테스트 케이스 질문

0

34

2

코살 문제풀이 환경

0

46

2

2 - T 오큰수 문제가 있는 것 같습니다.

0

43

1

추천 추가문제들

0

43

2

프로그래머스 코테 환경 관련해서 질문드립니다.

0

45

2

해당 문제에 대한 채점이 코딩살구클럽에서 올바르게 처리되지 않습니다.

0

40

2

균형 이진 트리 설명 시 높이 숫자

0

30

2

4-H 질문드립니다.

0

35

2

1-K 질문드립니다.

0

41

2

대기업 인적성 시험 질문

0

41

2

4-C 질문드립니다

0

41

2

[수학숙제 / BOJ 2870] 채점 서버 오작동

0

37

1

코테 준비 질문

0

50

1

살구클럽가입 요청드려요

0

39

2

1-I 문제 질문

0

40

2

코딩살구클럽 가입

0

57

2

AI 코딩 도구 사용 시 학습 방법 조언

0

51

2

코딩살구클럽 오류

0

61

2

코살클 [3-F 괄호 추가하기] 프라이빗 9번 제보

0

46

1

코딩살구클럽 테스트 케이스 오류 제보

0

52

2

삼성 코딩테스트

0

64

2

틀린 이유를 못찾겠습니다

0

48

2