ErdosNumbers/차영권

소감

2005/04/22 04:11:31.674 Time Limit Exceeded 0:10.047 444 Time Limit 나올꺼 같았다. 루프의 사용이 깔끔하지 못한거 같다.

코드

// erdosNumbers.cpp
#include <iostream.h>
#include <cstring>

#define MAX_LENGTH 100

struct Author
{
	char name[10];
	int erdosNumber;
};

void checkErdosNumberTo0(Author *p, int n);
void checkErdosNumberTo1(Author *p, char *c, int n);
void checkErdosNumberTo2(Author *p, int n);
bool isThere(Author *p, int n);
			
int main()
{
	int scenario=1;
	while (1)
	{
	int nDataBase, nSearch;
	int count = 0, n = 0, m = 0, number = 0;

	int i, j, k, l;
	int saveBound[10];
	char temp[MAX_LENGTH], *c;
	char search[10][20];
	Author author[10][30];

	cin >> nDataBase >> nSearch;
	cin.get();

	/* 입력받은 줄에서 이름을 추출한다 */
	while (count < nDataBase)
	{
		cin.getline(temp, MAX_LENGTH);
		c = temp;

		while (*(c-2) != ':')
		{
			author[m][number].name[n++] = *c;
			if (*c == '.' && (*(c+1) == ',' || *(c+1) == ':'))
			{
				author[m][number].name[n] = '\0';
				number++; n=0; c++; c++;
			}				
			c++;
		}
		temp[0] = '\0';
		saveBound[count] = number;
		m++; count++; number=0;
	}

	int save[10] = {0, };
	int count2 = 0;
	count=0; n=0;
	for (i=0 ; i<m ; i++)
	{
		for (j=0 ; j<saveBound[i] ; j++)
		{
			// 줄에 에르되시가 있다면..
			if (strcmp(author[i][j].name, "Erdos, P.") == 0)
			{
				for (k=0 ; k<saveBound[i] ; k++)
				{
					if (k == j)
						continue;
					else
					{
						for (n=0 ; n<m ; n++)
							checkErdosNumberTo1(author[n], author[i][k].name, saveBound[n]);
					}
				}					
				author[i][j].erdosNumber = -1;
				count2++;
			}
		}
		if (count2 == 0)
			save[count++] = i;
		count2 = 0;
	}

	for (i=save[number] ; i!=0 ; i=save[++number])
	{
		for (j=0 ; j<saveBound[i] ; j++)
		{
			if (isThere(author[i], saveBound[i]))
				checkErdosNumberTo2(author[i], saveBound[i]);
			else
				checkErdosNumberTo0(author[i], saveBound[i]);
		}
	}

	for (i=0 ; i<nSearch ; i++)
		cin.getline(search[i], 20);

	l = i;
	k = 0;

	int saveResult[10]={0,};

	while (k < l)
	{
		for (i=0 ; i<m ; i++)
		{
			for (j=0 ; j<saveBound[i] ; j++)
			{
				if (strcmp(search[k], author[i][j].name) == 0)
					saveResult[k] = author[i][j].erdosNumber;
			}
		}
		k++;
	}

	cout << "Scenario " << scenario++ << endl;

	for (i=0 ; i<l ; i++)
	{
		cout << search[i] << " ";
		if (saveResult[i] == 2)
			cout << "infinity" << endl;
		else
			cout << saveResult[i] << endl;
	}
	}

	return 0;
}

void checkErdosNumberTo0(Author *author, int n)
{
	for (int i=0 ; i<n ; i++)
		author[i].erdosNumber = 0;
}

void checkErdosNumberTo1(Author *author, char *name, int n)
{
	for (int i=0 ; i<n ; i++)
	{
		if (strcmp(author[i].name, name) == 0)
			author[i].erdosNumber = 1;
	}
}

void checkErdosNumberTo2(Author *author, int n)
{
	for (int i=0 ; i<n ; i++)
	{
		if (author[i].erdosNumber == 1)
			continue;
		else
			author[i].erdosNumber = 2;
	}
}

bool isThere(Author *author, int n)
{
	for (int i=0 ; i<n ; i++)
	{
		if (author[i].erdosNumber == 1)
			return true;
		else
			continue;
	}
	return false;
}