백준 1068 트리 C 풀이 - 트리

아주아주 간단한 문제.. 인 줄 알았는데 2시간은 쓴 것 같다.

문제 자체는 아주 간단하다.

트리를 만들고 자르라는걸 자르고 leaf의 개수를 세면 된다.

 

틀린 지점은 3곳이다.

1. 0%에서 틀렸다면, 배열이 항상 0번 인덱스가 Root로 나오는 것은 아니라는 것을 파악하고 다시 코드를 짜야한다.

혹은 루트를 잘랐을 경우를 고려하지 않았을 수 있다.

다음 예시를 참고해보자

3

1 -1 1

0

정답) 1

 

3

-1 0 0

0

정답) 0

 

2. 77%에서 틀렸다면, 자식이 2개라고 생각하고 구현했을 가능성이 높다.

5

-1 0 0 0 0

3

정답) 3

 

3. 99%에서 틀렸다면 Root만 남았을 경우에 틀렸을 가능성이 높다.

5

-1 0 1 2 3

1

정답) 1

 

고생한 점은 다음과 같다.

1. 그림에 낚여서 자식이 2개인 트리인 줄 알았다. 사실은 1개의 루트에 나머지 49개가 전부 붙어있을 수도 있다.

2. 루트를 자를 경우를 생각해줘야한다. 탐색하지 않고 바로 return 하도록 구현했다.

3. 루트만 남았을 경우를 생각해줘야한다. 루트만 남아있으면 leaf는 1개가 된다.

 

처음에는 calloc을 사용해서 동적인 할당을 해주었지만 인풋으로 들어오는 배열이 자신의 부모의 node번호를

갖고 있으므로 배열로 tree를 만들어 O(1)시간에 접근하는 것이 더 편해보여서 배열로 구현했다.

 

typedef struct st {
int node;
int p;
st* parent;
st* child[51];
}TREE;
TREE tree[51];

구조체를 이용하여 트리구조를 만든다.

node 는 자기 자신의 node번호이며(사실 배열의 번호와 같다) p는 자기 부모 node번호, parent 는 

부모의 주소, child는 자식의 주소를 저장한다. 51 크기로 선언한 이유는, 하나에 모든 node가 달렸을 수도 있기 때문이다.

 

나머지 논리구조는 쉽다.

1. 트리를 만든다(makeTree -> push(부모노드, 자식노드) 부모노드 child에 자식노드 연결, 자식노드 parent에 부모연결)

2. 자르라는 node를 자른다(Cut) - root를 자를경우 1을 리턴하여 즉시 종료. 부모의 child 배열 중 자기를 가리키는거 삭제

3. leaf를 센다(findLeaf) - root에서 출발하여 자식이 아무도 없을 경우 ans++ 아니라면 더 탐색

 

 

전체코드

#include <stdio.h>
#include <stdlib.h>
int N;
int cut;
int input[51];
int ans;
typedef struct st {
	int node;
	int p;
	st* parent;
	st* child[51];
}TREE;
TREE tree[51];

int findLeaf(TREE* p) {
	int tmp = 0;
	for (int i = 0; i < 51; i++) {
		if (p->child[i] != 0x0) break;
		tmp++;
	}
	if (tmp==51) {
		ans++;
		return 0;
	}
	for (int i = 0; i < 51; i++) {
		TREE* next = p->child[i];
		if (next == 0x0) continue;
		findLeaf(next);
	}
	return 0;
}
int Cut(int root) {
	if (cut == root) {
		return 1;
	}
	for (int i = 0; i < 51; i++) {
		if (&tree[cut] == tree[cut].parent->child[i]) {
			tree[cut].parent->child[i] = 0x0;
			break;
		}
	}
	return 0;
}

int push(TREE* parent,TREE * child) {

	for (int i = 0; i < 51; i++) {
		if (parent->child[i] == 0x0) {
			parent->child[i] = child;
			child->parent = parent;
			return 1;
		}
	}
	return 0;
	
}

void makeTree(int rootnode) {
	
	for (int i = 0; i < N; i++) {
		int pnode = input[i];
		tree[i].p = pnode;
		tree[i].node = i;
		if (pnode == -1)continue;
		push(&tree[pnode], &tree[i]);
	}

}

void print(TREE * p) {
	for (int i = 0; i < 2; i++) {
		if (p->child[i] != 0x0) {
			print(p->child[i]);
		}
	}
	printf("node : %d parent %d\n", p->node, p->p);
	return;
}

int main() {
	scanf("%d", &N);
	int a;
	for (int i = 0; i < N; i++) {
		scanf("%d", &input[i]);
		tree[i].node = i;
		tree[i].p = input[i];
		//root
		if (input[i] == -1) a = i;
	}
	//print(&ROOT);
	makeTree(a);

	scanf("%d", &cut);
	//루트를 잘랐을경우
	if (Cut(a)) {
		printf("0"); return 0;
	}
	//print(&ROOT);
	findLeaf(&tree[a]);

	printf("%d", ans);
	return 0;
}