U E D R , A S I H C RSS

Erdos Numbers/문보창

소감

소드

~cpp 
//#include <fstream>
#include <iostream>
#include <cstdlib>
using namespace std;

//fstream fin("input.txt");

const int MAX_STR = 20;
const int MAX_ERNUM = 100;

typedef struct Node * pNode;
typedef struct Node 
{
	char name[MAX_STR];
	pNode next;
};

pNode head[MAX_ERNUM];
int ernum;

void set_configuration();
void init();
void input_thesis(int num_thesis);
void input_writer(int num_writer);
bool slice_str(char * thesis);
bool make_map(char name[][MAX_STR], int num);
void insert_list(char * name);
int serch_erdos_num(char * name);

int main()
{
	set_configuration();
	int num_case, num_thesis, num_writer;
	cin >> num_case;
	for (int i = 0; i < num_case; i++)
	{
		init();
		cin >> num_thesis >> num_writer;
		cin.get();
		input_thesis(num_thesis);
		cout << "Scenario " << i + 1 << endl;
		input_writer(num_writer);
	}
	return 0;
}

void set_configuration()
{
	pNode temp;
	for (int i = 0; i < MAX_ERNUM; i++)
	{
		temp = new Node[sizeof(Node)];
		temp->next = NULL;
		head[i] = temp;
	}

	temp = new Node[sizeof(Node)];
	temp->next = NULL;
	head[0]->next = temp;
	strcpy(head[0]->next->name, "Erdos, P.");
}

void init()
{
	for (int i = 1; i < MAX_ERNUM; i++)
		head[i]->next = NULL;
	ernum = 0;
}

void input_thesis(int num_thesis)
{
	// 메모리 할당
	char ** thesis = new char * [num_thesis];
	for (int i = 0; i < num_thesis; i++)
		thesis[i] = new char[100];
	bool * ischeck = new bool[num_thesis];

	ernum++;

	for (i = 0; i < num_thesis; i++)
	{
		cin.getline(thesis[i], 100, ':');
		while (cin.get() != '\n')
			continue;
		ischeck[i] = slice_str(thesis[i]);
	}
	/* 여기까지가 에르되시의 수 1을 구한다. */

	bool iscontinue = true;
	while (iscontinue)
	{
		ernum++;
		iscontinue = false;
		for (i = 0; i < num_thesis; i++)
		{
			if (ischeck[i] == false)
			{
				ischeck[i] = slice_str(thesis[i]);
				if (ischeck[i] == true)
					iscontinue = true;
			}
		}
	}
	delete [] ischeck;
	for (i = 0; i < num_thesis; i++)
		delete thesis[i];
	delete thesis;
}

bool slice_str(char * thesis)
{
	char name[10][MAX_STR];
	int num_person = 0;
	int rest_count = 0;
	int i, j;
	i = j = 0;

	while (thesis[i] != NULL)
	{
		if (thesis[i] == ',')
			rest_count++;
		if (rest_count == 2 && thesis[i] == ',')
		{
			name[num_person][j] = '\0';
			num_person++;
			j = -1;
			rest_count = 0;
			if (thesis[i+1] == ' ')
				i++;
		}
		else
			name[num_person][j] = thesis[i];
		i++;
		j++;
	}
	name[num_person][j] = '\0';
	bool isMake = make_map(name, num_person + 1);		// 맵에 추가되었다면
	return isMake;

}

bool make_map(char name[][MAX_STR], int num)
{
	bool isCheck = false;
	bool * isInserted = new bool[num];
	for (int i = 0; i < num; i++)
		isInserted[i] = 0;

	pNode temp = head[ernum-1]->next;

	while (temp != NULL)
	{
		for (int i = 0; i < num; i++)			
		{
			if (strcmp(name[i], temp->name) == 0)
			{
				isCheck = true;
				isInserted[i] = 1;
			}
		}
		temp = temp->next;
	}
	
	if (isCheck)	// 기존 맵에 존재한다면 추가
	{
		for (int i = 0; i < num; i++)
		{
			if (isInserted[i] == false)		// 아직 추가되지 않았다면 추가
				insert_list(name[i]);
		}
	}
	delete [] isInserted;
	return isCheck;
}

void insert_list(char * name)
{
	pNode temp = head[ernum];
	while (temp->next != NULL)
		temp = temp->next;
	pNode ptr = new Node[sizeof(Node)];
	strcpy(ptr->name, name);
	ptr->next = NULL;
	temp->next = ptr;
}

int serch_erdos_num(char * name)
{
	pNode temp;
	for (int i = 0; i <= ernum; i++)
	{
		temp = head[i]->next;
		while (temp != NULL)
		{
			if (strcmp(temp->name, name) == 0)
				return i;
			temp = temp->next;
		}
	}
	return -1;
}

void input_writer(int num_writer)
{
	char name[20];
	int result;
	
	for (int i = 0; i < num_writer; i++)
	{
		cin.getline(name, 20, '\n');
		cout << name << " ";
		result = serch_erdos_num(name);
		if (result == -1)
			cout << "infinity\n";
		else
			cout << result << endl;
	}
}

나한테 할 말

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:13
Processing time 0.0128 sec