inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

2-R

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

223

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

큰돌

안녕하세요 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를 증가시킬 때 제가 하는 방법으로 증가시킬 경우에는 통과되지 않네요...

3-D 관련 질문

0

19

2

코살구 회원가입 문의

0

23

2

코살구 로그인 문제

0

49

2

3-A 문제 풀이 관련 질문

0

44

3

2-O 질문 있습니다

0

35

2

2-T 문제에 관한 질문

0

36

2

코딩 살구 클럽 접속 및 사용방법 문의

0

51

2

안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~

0

63

2

코딩살구클럽 로그인문제

0

69

3

코딩 살구 클럽 로그인 문제

0

75

2

2-J 채점관련 질문

0

65

3

코딩 살구 클럽 Python 지원 가능 여부

0

75

1

살구클럽 아이디 없음 문제

0

74

1

1-O 코딩살구클럽 채점관련 질문

0

57

2

히든 테스트 케이스가 사라졌습니다

0

55

1

채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요

1

73

2

살구 클럽 채점 관련 문의(테스트 케이스)

0

65

2

1-H 문제 채점하기 오류

0

58

3

코딩살구클럽 2주차 2-L 문제 채점하기 오류

0

52

2

살구 클럽 채점 관련 문의

0

62

2

코딩 살구 클럽 실전 세션

0

57

2

코딩살구클럽 채점 관련 질문

0

50

2

코딩살구클럽 컴파일에러

0

79

2

5-B

0

49

2