[백준] 트리 (1068번)

문제

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 중 하나를 제거할 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 제거한다고 하면, 다음과 같이 된다.

이제 리프 노드의 개수는 1개이다.

입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

출력

첫째 줄에 입력으로 주어진 트리에서 입력으로 주어진 노드를 지웠을 때, 리프 노드의 개수를 출력한다.

---

특정 노드를 제거한다는 점에서 처음에 어떻게 해결할지 약간 고민을 한 문제이다.

트리이고 그래프라는 점에서 착안해서 bfs로 풀기로 했다.

일단 링크드리스트 벡터를 이용해 각 노드마다 이어진 자식노드를 저장한다. 

-1이 입력으로 들어오면 루트 노드로 따로 지정하고, 삭제할 deleteNode도 전역변수로 지정해준다.

 

bfs로 들어가서 루트에 방문여부 1을 지정해준다. 

큐에 루트를 넣은 후 while문에서 x에 연결된 자식들을 차례대로 조사한다. 

만약 자식노드가 deleteNode와 같거나 이미 방문한 지점인 경우 continue로 조사를 하지 않는다.

아니라면 큐에 nx를 넣고 visit[nx]도 1로 저장한다.

자식이 있으면 visit[x]는 +1 해준다. 

bfs를 모두 마친 후 visit가 1인 인덱스의 개수를 세서 출력한다. visit가 1이라는 건 단말노드라는 것과 같기 때문이다.

 

제출한 후 오답이 떴었는데 root와 deleteNode가 같은 예외를 생각하지 않았기 때문이다.

예외까지 처리하고 정답을 받았다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8A%B8%EB%A6%AC(1068%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> tree[51];
int visit[51];
int N, root, res;
int deleteNode;

void bfs()
{
	memset(visit, 0, sizeof(visit));
	queue<int> q;
	if (root == deleteNode) return;
	q.push(root);
	visit[root] = 1;

	while (!q.empty()) {
		int x = q.front();
		q.pop();

		for (int i = 0; i < tree[x].size(); i++) {
			int nx = tree[x][i];
			if (nx == deleteNode || visit[nx] != 0) continue;
			q.push(nx);
			visit[x]++;
			visit[nx] = 1;
		}
	}
}

int main()
{
	cin >> N;
	for (int tmp, i = 0; i < N; i++) {
		cin >> tmp;
		if (tmp == -1) root = i;
		else tree[tmp].push_back(i);
	}
	
	cin >> deleteNode;
	bfs();

	res = 0;
	for (int i = 0; i < N; i++) 
		if (visit[i] == 1)
			res++;
	
	cout << res;
}