2-R 질문입니다

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

2-R

작성

301

수정됨

안녕하세요 선생님,

답안을 보며 제가 작성했던 코드의 로직만 변경해보는데 아무리 해도 통과되질 않았습니다. 설마 하고 child++ 부분을 건드렸는데 통과되길래 이번엔 답안의 child++부분만 제가 작성했던 대로 바꿨더니 통과하지 못했습니다.

child == 0을 체크하는 것과 adj[here].size() == 0을 체크하는 것은 같은 동작을 해야할 것으로 보이는데 차이가 발생하는 것이 이해가 가지 않아 질문을 드립니다. 왜 size() == 0 방식은 틀리는 것인가요?

http://boj.kr/754400230cc34e12826f100050bfe9eb

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 수강생님 ㅎㅎ

자 예를 들어 이런 트리가 있다고 해볼게요. 저 노드는 지워지는 노드입니다. 자 그러면 저 위에 있는 노드는 리프노드가 되어야 겠죠?

그러나 수강생님이 작성하신 코드, 즉, adj[here].size()만을 체크해서는 그러한 것을 파악할 수 없겠죠?

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

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

감사합니다.

강사 큰돌 올림.

dlsvmfjsrkddml

질문자

감사합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요.

child == 0과 adj[here].size() == 0은 같은 동작을 하는 것처럼 보여도 서로 다른 동작을 합니다.

child == 0은 해당 노드의 자식 노드의 개수를 체크하는 것이고, adj[here].size() == 0은 해당 노드의 인접한 노드의 개수를 체크하는 것입니다.

따라서, size() == 0을 체크하는 방식은 해당 노드의 인접한 노드가 없을 때만 해당되지만, child == 0은 해당 노드의 자식 노드가 없을 때도 해당됩니다.

즉, 자식노드가 없는 노드뿐만 아니라 인접한 노드가 없는 노드들을 체크하기 위해선 child == 0을 사용하여야 합니다.

이번 문제에서는 인접한 노드가 없는 경우에 해당하기 때문에 size() == 0도 정답처리 됩니다. 하지만, 문제에서 명시되지 않은 다른 케이스에서는 size() == 0 방식이 틀릴 수 있습니다.

해당 설명으로 인해 이해가 되셨는지요? 추가적으로 궁금하신 점이 있으면 언제든지 물어보세요!

dlsvmfjsrkddml

질문자

그런데 정답 원본에서는 다음과 같이 adj[here] 원소가 있는 경우 child++을 하고 있습니다. size() != 0일 경우 반드시 child수가 늘어나고 size() == 0일 경우 child 카운트가 아예 되지 않기 때문에 테스트 케이스가 달라지더라도 같은 동작을 하게 되지 않나요? 어쩌면 질문 내용에 코드가 없어서 ai가 잘못 인식한 듯 해서 두 종류의 코드를 첨부합니다.

int dfs(int here){
    int ret = 0;
    for(int there : adj[here]){
        if(there == r) continue;
        ret += dfs(there);
    }
    if(adj[here].size() == 0) return 1;
    return ret;
}

int dfs(int here){
    int ret = 0;
    int child = 0;
    for(int there : adj[here]){
        if(there == r) continue;
        ret += dfs(there);
        child++;
    }
    if(child == 0) return 1;
    return ret;
}

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

2-R 질문입니다