[백준][bfs] 1068 트리 c++ 구현

 

목차

 

 

https://www.acmicpc.net/problem/1068

1068번: 트리

문제

 

 

문제 구현 방향

이진 트리가 아니기 때문에 인접리스트를 통해서 문제를 접근하였다.

삭제는 bfs를 통해 탐색하여 삭제 노드를 표시하는 방법으로 접근했다.

 

 

 

 

문제 풀이

예시 입력)

9
1 6 4 1 3 3 8 8 -1
3

 

0
1	0	3
2
3	4	5
4	2
5
6	1
7
8	6	7

(단방향 인접 리스트)

 

 

 

 

 

 

 

그래프와 인접리스트로 표현한 모습이다.

 

 

 

0
1	0	3
6	1
7
8	6	7

 

 

 

 

 

 

 

bfs를 통해 삭제 표시를 해주고 탐색 대상에서 제외한다.

그 이후 각 원소의 사이즈가 0인 것만 세어주면 된다.

 

 

 

0
1	0	3
6	1
7
8	6	7

 

이 때 3은 삭제표시를 하지않았기 때문에 예외처리를 해주어야 한다.

3은 없는 것으로 취급하여 1의 사이즈는 1이다.

 

 

 

사이즈가 0인 것은 0과 7로 답은 2이다.

 

 

 

 

코드 구현

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int> tree[1000];  //인접리스트
vector<bool> visit(1000); //삭제한 노드 표시용
int cnt =0;

void bfs(int start) {
	queue<int> q;
	q.push(start);
	visit[start] = true;
	
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		
		for (int i = 0; i < tree[x].size(); i++) {
			int y = tree[x][i];

			if (!visit[y]) {
				visit[y] = true;
				q.push(tree[x][i]);
			}
		}
	
	}
	
}


int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n, deln, i, j;
	int num;
    
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (num == -1) {
			continue;      //-1이면 부모노드 존재 x
		}
		tree[num].push_back(i);  //단방향 인접 리스트임
		
	}
	
	cin >> deln;
	bfs(deln);
	
	for (i = 0; i < n; i++) {
		int cnt2 = 0;  
		if (!visit[i]) {
			for (j = 0; j < tree[i].size(); j++) {
				if (tree[i][j] != deln)   //삭제노드 예외처리
					cnt2++;
			}
			if (cnt2 == 0) {  //원소의 개수가 0이면 카운트 증가
				cnt++;
			}
		}
	
	}
	cout << cnt;


}