티스토리 뷰
728x90
https://www.acmicpc.net/problem/1068
C++ 트리
트리에서 어느 한 노드를 루트노드로하는 서브트리를 모두 삭제할때
리프노드 개수를 구하는 문제
접근방법
벡터로 인접리스트를 구현하고, 부모노드 정보를 담고 있는 1차원 배열을 생성한다.
인접리스트를 탐색하면서 기존 트리에서의 리프노드 개수를 카운팅한다.
지울 노드를 큐에 넣고 그 하위의 노드들도 큐에 넣어 삭제해주면서 지우는 노드가 리프노드인 경우
기존 리프노드 개수 - 1 한다.
이때 처음 지우는 노드의 부모노드가 자식을 지울노드 하나만 갖고 있다면
노드를 삭제하고 난 후 리프노드가 하나 더 생기는 셈이기 때문에 리프노드 개수 + 1 해줘야한다.
이때문에 부모노드 정보를 담고 있는 배열이 필요했다.
소스코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
//init & input
int n;
cin >> n;
vector<vector<int>> adj(n);
int parent[n];
int leaf = 0;
int node;
for(int i = 0 ; i < n ; i++){
cin >> node;
parent[i] = node;
if(node != -1){
adj[node].push_back(i);
}
}
int remove;
cin >> remove;
//process
for(int i = 0 ; i < n ; i++){
if(adj[i].empty())
leaf++;
}
queue<int> q;
q.push(remove);
if(parent[remove] != -1 && adj[parent[remove]].size() == 1){
leaf++;
}
while(!q.empty()){
int parent = q.front();
q.pop();
if(adj[parent].empty()){
leaf--;
}
for(int i = 0 ; i < adj[parent].size() ; i++){
q.push(adj[parent][i]);
}
}
//output
cout << leaf;
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 9660] 알고리즘 128일차 : 돌게임 6 (0) | 2021.08.31 |
---|---|
[백준 2467] 알고리즘 NCT???일차 : 용액 (0) | 2021.08.30 |
[백준 5639] 알고리즘 125일차 : 이진 검색 트리 (0) | 2021.08.24 |
[백준 1991] 알고리즘 124일차 : 트리 순회 (0) | 2021.08.23 |
[백준 11725] 알고리즘 123일차 : 트리의 부모 찾기 (0) | 2021.08.18 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Swift
- 자바
- 스택
- 투포인터
- 최단경로
- 그리디 알고리즘
- 백트래킹
- 트리
- 스위프트
- 다이나믹프로그래밍
- 프로그래머스
- 이분탐색
- 큐
- 백준
- 브루트포스
- 우선순위큐
- 정렬
- 알고리즘
- 최소힙
- BFS
- 그리디알고리즘
- 웹크롤링
- 게임이론
- dp
- 최대힙
- c++
- 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 |
글 보관함