inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

2-R

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

212

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

2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.

0

7

2

2주차 개념#12 트리 순회

0

19

2

백준사이트가 종료된다고 합니다.

0

225

2

백준 서비스 종료

9

719

1

sk 하이닉스 코테 대비

0

352

2

3-G 최댓값 질문

0

50

1

모듈러 연산 값이 10이 아닌 경우도 있지 않나요?

0

82

2

3-I 코드 질문드립니다.

0

61

2

3-N 질문 있습니다.

0

66

2

학습방법

0

100

2

4-H 질문 있습니다 (코드 리뷰)

0

66

2

코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.

0

164

2

2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.

0

69

2

2주차 개념 #4-2. 인접행렬 질문있습니다.

0

63

2

1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.

0

49

2

조합 재귀 풀이 확인 해주시면 감사하겠습니다.

0

67

2

함수별 시간복잡도

0

72

2

3-h 질문입니다.

0

49

1

안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.

0

52

2

1-I 문제 질문 드립니다.

0

76

2

2-P 질문입니다.

0

56

1

mac에서 시작하기 관련

0

88

2

5-Q 질문

0

63

2

풀이 코드 질문

0

63

2