코딩테스트/백준
[백준][C++]1068번 트리
윤깡패
2023. 6. 3. 23:32
문제
https://www.acmicpc.net/problem/1068
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
풀이
트리(Tree) 자료구조
트리(Tree) 자료구조 노드와 에지로 연결된 그래프의 특수한 형태 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 에지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리
soobin0821.tistory.com
코드
#include <iostream>
#include <vector>
using namespace std;
void deleteNode(int n);
static int N;
static vector<int> parent;
static vector<vector<int>> children;
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
parent.resize(N + 1);
children.resize(N + 1);
for(int i = 0; i < N; i++)
{
int num;
cin >> num;
parent[i] = num;
if(num != -1)
{
children[num].push_back(i);
}
}
int del;
cin >> del;
deleteNode(del);
int leaf = 0;
for(int i = 0; i < N; i++)
{
if(parent[i] != -2 && children[i].size() == 0)
{
leaf++;
}
}
cout << leaf;
return 0;
}
void deleteNode(int n)
{
parent[n] = -2;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < children[i].size(); j++)
{
if(children[i][j] == n)
{
children[i].pop_back();
}
}
}
for(int child : children[n])
{
deleteNode(child);
}
}
728x90