[코딩테스트] 백준 1068번 트리

문제 : https://www.acmicpc.net/problem/1068

문제 

노드를 지우면, 자식노드까지 전부 삭제하는 문제이다

입력 & 출력

입력

출력

5

-1 0 0 1 1
1

즉, 이 트리는 루트노드는 아무런 부모를 가지고 있지 않고, 

1번 / 2번 노드는 0번 노드 (루트 노드)를 부모 노드로 가지고 있으며

3번 /4번 노드는 1번 노드를 부모 노드로 가지고 있다.

따라서 1번 노드를 지우게 되면 루트노드와 2번 노드만 남으므로

최종 남는 리프노드의 개수는 1개이다.

1 이 출력된다.

 

풀이

#include <stdio.h>

using namespace std;

int tree[51];
int N;

void deleteA(int x){
    tree[x] = -2;
    for(int i = 0; i < N; i++){
        if(tree[i] == x){
            deleteA(i);
        }
    }


}
int main()
{
    int a;
    int l = 0;
    int flag;

    scanf("%d", &N);

    for(int i = 0; i < N; i++){
        scanf("%d", &tree[i]);
    }

    scanf("%d", &a);

    deleteA(a);

    for(int i = 0; i < N; i++){
        flag = -3;
        for(int j = 0; j < N; j++){
            if( i == tree[j]){
                flag = -1;
            }
        }
        if(flag == -3 && tree[i] != -2) l++;
    }

    printf("%d", l);
    return 0;

}

delateA라는 함수를 통해 어떠한 노드를 삭제하면, 이 노드의 자식노드들까지 재귀적으로 삭제되는 함수를 만들었다.

배열은 그대로 두되, -2라는 삭제된 상태임을 인지하면 노드의 개수를 세지 않아, 최종적으로 몇 개의 리프노드가 남았는지 출력하는 프로그램이다.

 

피드백

거의 자료구조적인 문제로만 풀었는데, DFS를 사용하면 시간을 더 줄일 수 있을 것 같다.