티스토리 뷰
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
- 가장 큰 수 프로그래머스
- 투포인터
- 동적계획법
- 트리
- BFS
- 알고리즘
- 최대힙
- 이분탐색
- c++
- 웹크롤링
- 스택
- 백준
- 우선순위큐
- 최단경로
- 게임이론
- 최소힙
- 정렬
- 브루트포스
- 가장 큰 수 Swift
- Swift
- 파이썬
- 다이나믹프로그래밍
- dfs
- 백트래킹
- 토마토
- 자바
- 수학
- 프로그래머스
- dp
- 그리디알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함