[C] 백준 - 1068번: 트리

8월 31일(목) - 트리 (1068번)

1068번: 트리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(풀이출처 -> https://forswdev.tistory.com/entry/%EB%B0%B1%EC%A4%80-1068-%ED%8A%B8%EB%A6%AC-C-%ED%92%80%EC%9D%B4-%ED%8A%B8%EB%A6%AC)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int N;
int input[51];
int del_node;
int ans;

typedef struct Treenode {
	int node;
	int p;
	struct Treenode* parent;
	struct Treenode* child[51];
}Treenode;

Treenode tree[51];

void make_tree(int root)
{
	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]);
	}
}

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

	return 0;
}

int delete(int root)
{
	if (del_node == root)
	{
		return 1;
	}
	for (int i = 0; i < 51; i++)
	{
		if (&tree[del_node] == tree[del_node].parent->child[i])
		{
			tree[del_node].parent->child[i] = 0x0;
			break;
		}
	}

	return 0;
}

int findLeaf(Treenode* 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++)
	{
		Treenode* next = p->child[i];
		if (next == 0x0)
		{
			continue;
		}
		findLeaf(next);
	}

	return 0;

}

int main(void)
{
	scanf("%d", &N);

	int a = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &input[i]);
		tree[i].node = i;
		tree[i].p = input[i];

		if (input[i] == -1)
		{
			a = i;
		}
	}

	make_tree(a);

	scanf("%d", &del_node);
	if (delete(a))
	{
		printf("0");
		return 0;
	}

	findLeaf(&tree[a]);

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(풀이출처 -> https://www.acmicpc.net/source/62971561)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

int parent[51][2];
int visited[51];
int count[51];
int leaf = 0;

void dfs(int v, int del, int n)
{
	visited[v] = 1;
	for (int i = 0; i < n; i++)
	{
		if ((parent[v][1] != 100) && (parent[i][1] == v) && !visited[i])
		{
			if (!count[i])
				leaf++;
			else
			{
				dfs(i, del, n);
			}
		}
	}
}
int main(void)
{
	int n;
	scanf("%d", &n);
	int tree;
	int index = 0;

	for (int i = 0; i <= n - 1; i++)
	{
		scanf("%d", &tree);
		parent[i][0] = i;
		parent[i][1] = tree;
		if (tree == -1)
		{
			index = i; count[i]++;
		}
		else
		{
			count[tree]++;
		}
	}

	int del;
	scanf("%d", &del);

	if (n == 2)
	{
		if (parent[del][1] == -1)
		{
			printf("0\n");
		}
		else
		{
			printf("1\n");
		}
	}
	else
	{
		count[parent[del][1]]--;
		parent[del][1] = 100;
		dfs(index, del, n);
		printf("%d\n", leaf);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ