[백준]트리

백준저지

[트리]https://www.acmicpc.net/problem/1068

 

• 문제를 푸는데 30분정도 걸렸다.

• 두 번 실패를 하였다.

→ 원인은 노드의 삭제가 재귀적인 성향을 가지고 있다는 것을 늦게 발견하였음

→ 즉, 삭제하려고 하는 노드를 포함한 자손까지 전부 삭제를 해주어야 됨

→ 일차원적으로 삭제하려고 하는 노드의 자식만 삭제하여 계속 실패를 하였음

 

[풀이]

• 삭제에 유용한 list STL을 사용하여 트리를 구성하였음(리스트 배열 51개를 생성)

• 입력 값들 중 두 번째 줄에서 부모 노드가 없는 경우는 루트 노드이기 때문에 따로 –1처리를 해주지 않았음

• 두 번째 줄에서 부모 노드를 입력 받기 때문에 listArr[51]의 인덱스를 노드의 번호로 간주, 인덱스르 이용해서 트리 그래프를 구성하였음

• 그리고 트리에서 삭제하고자 하는 노드를 지워주고 삭제하고자 하는 노드에 연결된 자손들을 재귀함수를 이용해서 삭제를 하였음

• -1은 다른 의미는 없고 삭제된 노드임을 뜻함

• 리프노드는 연결된 것이 없는 노드들을 카운트해주어서 개수를 출력하였음

#include <iostream>
#include <list>

using namespace std;

void removeNode(list<int> listArr[], int num) {
	if (listArr[num].empty())
		listArr[num].push_back(-1);
	else {
		while (!listArr[num].empty()) {
			int tmp = listArr[num].front();
			listArr[num].pop_front();
			removeNode(listArr, tmp);
		}
		listArr[num].push_back(-1);
	}
}

int main(void) {

	list<int> listArr[51];
	int cnt = 0, delNode;
	int num; cin >> num;

	for (int i = 0; i < num; i++) {
		int in; cin >> in;
		if (in != -1)
			listArr[in].push_back(i);
	}
	cin >> delNode;

	for (int i = 0; i < num; i++)
		listArr[i].remove(delNode);

	removeNode(listArr, delNode);

	for (int i = 0; i < num; i++) {
		if (listArr[i].empty())
			cnt++;
	}
	cout << cnt;

	return 0;
}