1068 트리

백준 1068 트리 : https://www.acmicpc.net/problem/1068

1068번: 트리

 

 

 

코드 작성 전, 하나의 노드에 대해 필요한 정보를

① 부모 값

② 자식의 수

로 정리하고,

 

리프 노드를 구하는 방법을,

자식의 수가 0인 노드의 부모 값, 부모의 부모 값 … 루트 노드 값까지

삭제한 노드 값과 일치하는 값이 없으면 리프 노드로 결정하는 방법으로 정했다. 

 

그리고 주의할 점,

루트 노드가 삭제될 경우

직선 상태에서 노드가 삭제된 경우 

 

#include <iostream>
using namespace std;


int main() {
	int n, p;
	cin >> n;

	int parent[50] = {}; // 노드 n의 부모 값
	int child[51] = {};  // 노드 n의 자식 여부(root = 0)

	for (int i = 0; i < n; i++) {
		cin >> p;
		parent[i] = p;
		child[p + 1]++;
	}

	// 삭제 
	int d;
	cin >> d;
	child[parent[d] + 1]--;


	// 리프 노드 찾기
	int leaf = 0;

	for (int i = 0; i < n; i++) { 
		int ip = parent[i];
		if (child[i + 1] == 0 && i != d) { // 자식이 없으면
			while (ip >= -1) {
				if (ip != d) {
					if (ip == -1) {
						leaf++;
						break;
					}
					ip = parent[ip];
				}
				else break;
			}
		}
	}

	cout << leaf;
	return 0;
}

 

int parent[50]	값이 n인 노드의 부모 노드 값
int child[51]	값이 n인 노드의 자식 노드 수  - 루트 노드 때문에 50 + 1로 설정(아니면 -1이 배열 범위를 벗어남)
int leaf	리프 노드 수를 저장하는 변수(정답)
while(ip >= -1) {}	① 현재 부모 노드의 값이 삭제된 노드의 값과 일치하는지 확인 ② 일치하지 않다면, 부모 노드의 부모 노드 값을 현재 확인하는 값으로 변경하여 확인 ③ 계속 일치하지 않는다면, 루트 노드 값까지 비교 ④ 루트 노드까지 값이 일치하지 않다면 리프 노드, 따라서 변수 leaf 값 증가

 

+)

문제를 이해하고 나면 어렵지 않은데,

이진트리로 착각해서 더 복잡하게 풀어서 시간을 더 쓴게 아쉽다.

 

문제의 명확하게 알고나서는 금방 풀 수 있었다.