[C++] 백준(BOJ) - 1068 : 트리
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.
예를 들어, 다음과 같은 트리가 있다고 하자.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.
이제 리프 노드의 개수는 1개이다.
입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
입력 예제
5
-1 0 0 1 1
2
출력 예제
2
알고리즘
- DFS - 인접리스트
- int형 DFS
풀이
- 트리는 루트 노드부터 탐색하여 한번에 탐색을 끝낸다
- erase의 두가지 방법
- 지운다
- 세지 않는다
- 반례 체크 - here-there 기반으로 로직을 짰다면 root 노드가 삭제됬을 때를 고려하여야 한다
코드
// BOJ - 1068 : 트리
#include <bits/stdc++.h>
using namespace std;
int n, root, k;
vector<int> adj[51];
// int형 DFS, 리프노드 수를 구하는 함수
int dfs(int here)
{
int res = 0, child = 0;
for (int there : adj[here])
{
if (there == k) continue;
res += dfs(there);
child++;
}
if (child == 0) return 1; // 자식이 없다면 리프노드
else return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
if (tmp == -1) root = i;
else adj[tmp].push_back(i);
}
cin >> k;
// DFS가 here -> there, there 기반 코드
if (k == root) cout << 0 << '\n'; // root 노드에 대한 반례 필요
else cout << dfs(root) << '\n'; // 트리는 루트노드부터 탐색을 하는 것이 유리하다
return 0;
}
평가
- 다양한 반환형태의 함수를 작성할 수 있다
- 트리문제의 경우 root 노드부터 탐색을 하여 한번에 탐색한다
- 반례 체크는 필수
