[C] 백준 - 11725번: 트리의 부모 찾기

8월 17일(목) - 트리 (11725번)

11725번: 트리의 부모 찾기

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

 

최초 생각 정리

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

 

문제점

#include <stdio.h>

int N;

int visited[100001];
int parent[100001];
int graph[100001][100001];

void dfs(int num)
{
	visited[num] = 1;

	for (int i = 0; i <= sizeof(graph); i++)
	{

	}
}

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

	for (int i = 0; i < N - 1; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		graph[x] = y;
		graph[y] = x;
	}

	dfs(1);
	
	for (int i = 2; i <= N; i++)
	{
		printf("%d\n", parent[i]);
	}

	return 0;
}

1. 2차원 배열로 graph를 저 사이즈로 설정할 수는 없다...그래서 malloc을 사용하고 난리를 쳐봐도 풀이 불가능

-> 그래서 풀이 참고

-> 추후 복습 및 재풀이 필요

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

 

풀이

(풀이출처 -> https://velog.io/@honeyricecake/11725번-트리의-부모-찾기)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int array[100001];// array[n]에는 n이랑 연결된 노드 개수 추가
int brray[100001];

typedef struct node
{
	int data;
	struct node* next;
}Node;

Node* Array[100001];

void dfs(int n)
{
	int i;
	Node* cur;

	cur = Array[n];

	for (i = 1; i <= array[n]; i++)
	{
		cur = cur->next;
		if (brray[cur->data] == 0)//brray에 저장된게 없으면 처음 만난게 부모 노드
		{
			brray[cur->data] = n;//array[n][i]의 부모노드로 n을 추가
			dfs(cur->data);//자식 노드를 찾으러 떠난다.
		}
	}
}

int main(void)
{
	int i, j, N;
	int x, y;
	int count = 0;
	Node* cur;

	scanf("%d", &N);

	for (i = 1; i <= N; i++)
	{
		Array[i] = (Node*)malloc(sizeof(Node));
		Array[i]->next = NULL;
	}

	for (i = 0; i < N - 1; i++)
	{
		scanf("%d %d", &x, &y);

		array[x]++;//array[x]에는 그 성분과 연결된 노드의 개수를 저장
		cur = Array[x];
		for (j = 0; j < array[x] - 1; j++)
		{
			cur = cur->next;
		}
		cur->next = (Node*)malloc(sizeof(Node));
		cur->next->data = y;
		cur->next->next = NULL;

		array[y]++;
		cur = Array[y];
		for (j = 0; j < array[y] - 1; j++)
		{
			cur = cur->next;
		}
		cur->next = (Node*)malloc(sizeof(Node));
		cur->next->data = x;
		cur->next->next = NULL;
	}

	dfs(1);

	for (i = 2; i <= N; i++)
	{
		printf("%d\n", brray[i]);
	}

	return 0;
}

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