출처 : https://www.acmicpc.net/problem/1068
트리 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 7550 | 1736 | 1448 | 26.232% |
문제
트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.
트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.
예를 들어, 다음과 같은 트리가 있다고 하자.
현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 제거한다고 하면, 다음과 같이 된다.
이제 리프 노드의 개수는 1개이다.
입력
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.
출력
첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.
예제 입력 1
5 -1 0 0 1 1 2
예제 출력 1
2
풀이
자식 노드의 개수를 세는 벡터를 생성합니다.
데이터가 들어오면 자식 노드의 개수를 전부 입력받습니다.
제거하는 노드의 번호를 받고, 자식 노드의 숫자를 확인하면서 dfs를 수행합니다.
dfs를 수행하면서 탐색하는 노드가 제거된 노드이면 리턴해줍니다.
그 다음으로는 자식의 개수에 따라서 달라집니다.
자식이 0개면 리프노드이기 때문에 정답에 1을 더해줍니다.
자식이 1개이면 해당 노드가 제거된 노드이면 리프노드이기 때문에 정답에 +1을 해주고, 아니면 dfs를 진행합니다.
자식이 2개 이상이면 dfs를 각각의 노드에 대하여 수행합니다.
자세한 구현은 소스코드를 참조해주세요~
소스코드
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 | #include <iostream> #include <algorithm> #include <vector> #pragma warning(disable:4996) using namespace std; #define MAX 50 + 1 // global vector<vector<int>> child_vec; int answer = 0, del_node; // 자식 노드를 dfs를 이용하여 센다. // 자식 노드가 1개 있으면, 해당 노드가 삭제할 노드인지 확인한다. void how_many_leaf(int now_node) { if (del_node == now_node) return; int ch_size = child_vec[now_node].size(); switch (ch_size) { case 0: answer++; return; break; case 1: if (child_vec[now_node][0] == del_node) { answer++; break; } default: for (int ch_idx = 0; ch_idx < ch_size; ch_idx++) how_many_leaf(child_vec[now_node][ch_idx]); break; } } int main() { // input 받아서 루트, 부모, 자식 처리하기 int N, root; scanf("%d", &N); child_vec.resize(N); for(int in_idx = 0; in_idx < N; in_idx++) { int parent; scanf("%d", &parent); if (parent != -1) child_vec[parent].push_back(in_idx); else root = in_idx; } scanf("%d", &del_node); how_many_leaf(root); printf("%d", answer); return 0; } | cs |