[BOJ] #1068 트리

시간 제한	메모리 제한	정답 비율
2초	128MB	25.526%

1068번: 트리

 

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

 

해결

key point, 루트노드가 0이 아닐 수도 있다.

계속 이상하게 틀리길래 질문 검색에서 반례를 찾아봤는데 정말 꿀같은 반례를 찾았다.

Testcase

7
3 6 6 -1 0 6 3
4

출력 → 4

테스트케이스를 도식화하면 위의 그림처럼 된다. 이 처럼 '둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다.'라고 문제에서 주어졌지만, 루트노드부터 순차적으로 주어진단 말은 없으므로 -1이 입력을 때 비로소 루트노드가 몇 번째 노드인지 알 수 있다.

또 유의할 점은,

루트노드가 삭제되면 답은 0이고,

편향트리일 때 리프노드 개수를 잘 세고 있는지 생각해봐야 한다.

처음에 했던 방식은
노드를 삭제할 때 노드 자체를 없애는 것이 아니라 의미에 집중하여 chk[] 배열에 1을 넣어서 이미 방문한 노드로 처리를 하고, 새롭게 루트부터 순환하며 해당노드에 자식이 없어야지만 개수를 셌다. → 인접리스트의 크기가 0일 때
그래서 편향트리일 때 리프노드를 삭제하면, 1이 출력되는 것이 아니라 0이 출력되었다.

이 부분을 해결하기 위해서 DFS함수 내에 cnt라는 지역변수를 두어서 0으로 초기화해둔 후 방문하지 않은 노드의 개수를 세어서 마지막까지 0이라면 리프노드라고 판단했다.

정리하자면

1. DFS
2. -1을 입력으로 받았을 때 루트노드가 정해진다.
3. 노드삭제는 물리적인 삭제가 아니라 방문한 노드로 체크했다.
4. 본격적으로 리프노드 탐색을 할 때 root부터 시작한다.
5. cnt가 0으로 유지될 때만 리프노드로 판단하여 ans를 증가시킨다.

모든 노드에 대한 탐색을 마친 뒤 ans을 출력하면 정답이다.

flg변수의 의미는 노드를 삭제할 때 ans변수에 변화가 있으면 안되므로 노드 삭제 후 flg를 1로 바꾸고 DFS(root) 탐색을 다시 진행했다.

 

코드

메모리	시간
1984KB	0ms

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int n, root, rm, chk[55], flg, ans;
vector<int> v[55];
void dfs(int num) {
    chk[num] = 1;
    int cnt = 0;
    for (auto child : v[num]) {
        if (chk[child]) continue;
        chk[child] = 1;
        cnt++;
        dfs(child);
    }
    if (flg && cnt == 0) ans++;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0, a; i < n; i++) {
        scanf("%d", &a);
        if (a == -1) { root = i; continue; }
        v[a].push_back(i);
    }
    scanf("%d", &rm);
    dfs(rm);
    flg = 1;
    if (rm != root) dfs(root);
    printf("%d", ans);
    return 0;
}

 

 

테스트케이스 첨부

트리 테스트케이스.txt

0.00MB