yjy1129   6년 전

DFS 형식으로 서치하는데 삭제한 노드를 기점으로 다 탐색할수 없게 DeleteTree라는 함수를 만들었습니다. 이때 삭제하는 노드가 리프노드이면 
부모 노드에서도 삭제하게끔 해서 리프노드 삭제시 카운팅 오류 나는 문제 해결한거 같은데 모든 경우를 다 잡지 못하는걸까요? ㅜㅜ 

atomzeno   6년 전

어.....  반례를 찾았다

직선이면 안되네

ex) 4 -1 0 1 2 2 넣으면 0 나오네요

단말노드 오류난다고 부모 제거하면 절대 안되요 ㅎㅎ

#include <iostream>
#include <vector>
#define MAX 50
using namespace std;
vector<int> adj[MAX];
bool check[MAX];
int n, root, d, cnt;
void DeleteTree(int root){
    check[root] = false;
}
void SearchTree(int root){
    if(check[root]==false){return;}
    int lll=0;
    for(int i = 0 ; i < adj[root].size(); i++){
        int child = adj[root][i];
        if(check[child] == true){
            lll++;
            SearchTree(child);
        }
    }
    if(lll==0){
        cnt++;
    }
}

int main(){
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        check[i] = true;
        int tmp;
        cin >> tmp;
        if(tmp == -1) root = i;
        else{
            adj[tmp].push_back(i);
        }
    }

    cin >> d;
    DeleteTree(d);

    SearchTree(root);

    cout << cnt << endl;

    return 0;
}



atomzeno   6년 전

그냥 틀렸던 이유는 

직선이면 주르륵 부모까지 지워서 0 나오고

그거 지우면, 자식노드가 1개일 때 하나가 잘리면 그게 단말도드인게 처리 안됨(size=1인데, 단말노드 됨)

그걸 처리할려고 visit가 true일때 개수를 셌어요. 그래서 0인 게 단말노드

yjy1129   6년 전

감사합니다! ㅜㅜㅜ 직선일때 생각을 못했네요 정말감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.