백준 #1068 트리

이번 문제는 트리에서 어떤 노드를 삭제하고 나서의 말단 노드(leaf node)의 갯수를 구하는 것입니다.

 

트리에서 1번 노드 삭제

위의 그림에서처럼 트리가 있는데, 1번 노드를 삭제하면, 3번 노드와 4번 노드도 같이 삭제되어서 2번 노드 하나만 말단 노드가 됩니다.  그 갯수를 구하면 됩니다.

 

난이도는 Silver I으로 되어 있지만, 구현은 어렵지는 않습니다.

 

문제의 원 링크입니다.

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

1068번: 트리

전 이 문제를 집합 자료 구조처럼 풀었습니다.  각각의 노드들은 부모 노드만 가르키고 있습니다.  삭제할 노드에는 삭제되었음을 알려주도록 부모값을 -2로 설정합니다.  그런 후에 모든 노드들 중, 자신이 부모가 아닌 노드들을 찾아갑니다.  노드의 value값이 설정되어 있으면 어떤 노드인가 자신을 부모로 삼았다는 이야기이므로 단말 노드가 될 수 없습니다.  결국 단말 노드들만 value값이 0이 됩니다.  단말 노드들은 자신의 부모를 찾아가기 위해서 최상위 조상을 찾아서 -1로 끝나면 단말노드 갯수를 카운팅하고 -2로 끝나면 넘어갑니다.

 

이 풀이법은 알고리즘 복잡도로 보았을 때, 각각의 단말 노드를 찾아가는 복잡도가 \(O(N)\)이고, 최상위 노드를 찾는 복잡도가 최악의 경우 \(O(N)\) 이지만, 최악의 경우란 것은 단말노드가 아주 적게 존재하는 경우이므로 실제로 전체 복잡도는 \(O(N \log{N} )\) 이 됩니다.  노드 갯수가 최대 50개이므로 알고리즘 효율성은 크게 상관은 없긴 합니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1068 - Tree
//    - by Aubrey Choi
//    - created at 2019-06-28
//----------------------------------------------------------------------------------------
#include <stdio.h>

struct Node { int value; int parent; };
int main()
{
  int n, p, k, root, ans = 0;
  static Node nodes[50];
  scanf("%d", &n);
  for(int i = 0; i < n; i++)
  {
    scanf("%d", &p);
    nodes[i].parent = p;
    if(p == -1) root = i; else nodes[p].value++;
  }
  scanf("%d", &k);
  if(nodes[k].parent >= 0) nodes[nodes[k].parent].value--;
  nodes[k].parent = -2;
  for(int i = 0; i < n; i++)
  {
    if(nodes[i].value) continue;
    p = nodes[i].parent;
    while(p >= 0) p = nodes[p].parent;
    if(p == -1) ans++;
  }
  printf("%d\n", ans);
}