2-R 질문입니다

작성한 질문수 9

0

안녕하세요 수강생님 ㅎㅎ

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

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

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

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

감사합니다.

강사 큰돌 올림.

0

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

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

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

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

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

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

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

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;
}