백준 알고리즘(C++)

백준 1068번 트리 ( C++ )

coding232624 2024. 3. 28. 11:11

문제

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

 

1068번: 트리

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

www.acmicpc.net

 

해설

트리를 이해하고 있는지 묻는 간단한 문제

1. 루트노드가 0이 아닐때

2. 루트노드가 삭제될때

3. 루트노드만 남을때

이 경우만 잘 고려하면 되는 문제

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
 
int visited[54], n, ret, tmp, X, root;
vector<int> mp[54];
 
void go(int g)
{
  visited[g] = 1;
  int child = 0;
  for (int i : mp[g])
  {
    if (!visited[i] && i != X)
    {
      go(i);
      child++;
    }
  }
  if (child == 0)
    ret++;
}
 
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> tmp;
    if (tmp == -1)
      root = i;
    else
      mp[tmp].push_back(i);
  }
 
  cin >> X;
  if (X == root)
  {
    cout << 0;
    return 0;
  }
  else
  {
    mp[X].clear();
    go(root);
  }
 
  cout << ret;
}
 cs