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

안녕하세요 도날드님 ㅎㅎ

반례는.. 아 있을 것 같은데 못찾았습니다...

다만. 이렇게 되어야 하지 않을까요?

해당 부분이 지워지면 -> 해당 부분을 부모노드로 하는 자식 노드들도 전부 삭제.

#include<bits/stdc++.h>
using namespace std;

int n, root, k, cnt;
vector<int> v[54];

void dfs(int from) {
    if(v[from].empty()) {
        cnt++;
        return;
    }
    
    for(int there : v[from]) {
        dfs(there);
    }
}

int main() {
    cin >> n;
    
    for(int i=0; i<n; i++) {
        int parent;
        cin >> parent;
        
        if(parent == -1) {
            root = i;
        } else {
            v[parent].push_back(i);
        }
    }
    
    cin >> k;
    
    for(int i=0; i<n; i++) {
        v[i].erase(remove(v[i].begin(), v[i].end(), k), v[i].end());
    }
    
    if(k == root) {
        cout << 0;
    }
    else {
        dfs(root);
        cout << cnt;
    }
    
    return 0;
}

다만..

	cin >> k;
	
	v[k].clear();

이렇게 해서 안되는 이유는.. 제가 찾으면 다시 답변 달겠습니다.

감사합니다.

안녕하세요, 인프런 AI 인턴입니다.
donald010님, 벡터를 활용한 트리의 노드 삭제 문제에서 반례를 찾는 것이 까다로울 수 있습니다.
해당 문제는 BOJ (Baekjoon Online Judge)의 문제인 것으로 보이고, 귀하께서 언급하신 루트 노드 삭제, 중간 노드 삭제, 리프 노드 삭제에 대한 처리를 확인하셨다고 하셨으나, 여전히 예외 상황이 발생할 수 있습니다.

특정 트리의 구성이나 입력 패턴에 의한 예외처리가 누락되었을 가능성, 혹은 삭제 과정에서 발생하는 인덱스 관리의 오류 등이 원인일 수 있습니다. 주로 트리를 배열이나 리스트로 구현할 때 발생할 수 있는 인덱스 오류, 포인터 오류를 주의깊게 검토하셔야 합니다.

이 외에도 특정 조건에서의 순회 중단, 재귀 호출의 깊이, 그리고 문제의 특수한 조건(자식 노드의 개수 제한, 노드 값의 범위 등)에 대한 처리가 올바르게 이루어졌는지 확인하셔야 합니다.

또한, Stack Overflow에서 비슷한 문제나 연관된 알고리즘에 대한 논의가 이루어지는 경우가 많으므로, 해당 사이트에서 tree, delete, vector 등의 태그를 활용하여 질문을 검색해보거나, 직접 질문을 올리실 수도 있습니다.

반례를 찾는 것이 쉽지 않다면, 간단한 케이스부터 복잡한 케이스로 단계별로 살펴보면서 코드를 한 줄 한 줄 디버깅해보는 것도 좋은 방법입니다. 혹은 동료 개발자나 멘토에게 코드를 보여주며 피드백을 받는 것도 도움이 될 수 있습니다.

코드에 대한 직접적인 검토가 필요한 경우라면, 더 상세한 코드와 실행 환경을 제공해주셔야 구체적인 도움이 가능합니다.

도움이 필요하시면 언제든지 문의해주세요. 화이팅입니다!