-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
2-R 질문입니다
23.05.29 12:07 작성 23.05.29 12:10 수정 조회수 270
0
안녕하세요 선생님,
답안을 보며 제가 작성했던 코드의 로직만 변경해보는데 아무리 해도 통과되질 않았습니다. 설마 하고 child++ 부분을 건드렸는데 통과되길래 이번엔 답안의 child++부분만 제가 작성했던 대로 바꿨더니 통과하지 못했습니다.
child == 0을 체크하는 것과 adj[here].size() == 0을 체크하는 것은 같은 동작을 해야할 것으로 보이는데 차이가 발생하는 것이 이해가 가지 않아 질문을 드립니다. 왜 size() == 0 방식은 틀리는 것인가요?
http://boj.kr/754400230cc34e12826f100050bfe9eb
답변을 작성해보세요.
0
큰돌
지식공유자2023.05.31
안녕하세요 수강생님 ㅎㅎ
자 예를 들어 이런 트리가 있다고 해볼게요. 
저 노드는 지워지는 노드입니다. 자 그러면 저 위에 있는 노드는 리프노드가 되어야 겠죠?
그러나 수강생님이 작성하신 코드, 즉, adj[here].size()만을 체크해서는 그러한 것을 파악할 수 없겠죠?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
인프런 AI 인턴
2023.05.31
안녕하세요, 인프런 AI 인턴이에요.
child == 0과 adj[here].size() == 0은 같은 동작을 하는 것처럼 보여도 서로 다른 동작을 합니다.
child == 0은 해당 노드의 자식 노드의 개수를 체크하는 것이고, adj[here].size() == 0은 해당 노드의 인접한 노드의 개수를 체크하는 것입니다.
따라서, size() == 0을 체크하는 방식은 해당 노드의 인접한 노드가 없을 때만 해당되지만, child == 0은 해당 노드의 자식 노드가 없을 때도 해당됩니다.
즉, 자식노드가 없는 노드뿐만 아니라 인접한 노드가 없는 노드들을 체크하기 위해선 child == 0을 사용하여야 합니다.
이번 문제에서는 인접한 노드가 없는 경우에 해당하기 때문에 size() == 0도 정답처리 됩니다. 하지만, 문제에서 명시되지 않은 다른 케이스에서는 size() == 0 방식이 틀릴 수 있습니다.
해당 설명으로 인해 이해가 되셨는지요? 추가적으로 궁금하신 점이 있으면 언제든지 물어보세요!
dlsvmfjsrkddml
질문자2023.05.31
그런데 정답 원본에서는 다음과 같이 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