PKU 1904. King's Quest. TLE

지환태 2009. 1. 23. 13:46

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

struct _prince_  
{  
	int love[2001];  
	int marry[2001];  
	int n;  
}prince[2001];

int married_girl[2001];
int n;

void input()  
{  
	int i, j ,k;  
	scanf("%d",&n);  
	for(i=0; i<n; i++)  
	{  
		scanf("%d",&j);  
		for(k=0; k<j; k++)  
		{  
			scanf("%d",&prince[i].love[k]);  
		}  
	}  
	for(i=0; i<n; i++)  
	{  
		scanf("%d",&j);//scanf("%d",&prince[i].marry[prince[i].n++]);  
	}  
}

int intcmp(int* pa, int* pb)  
{  
	return (*pa - *pb);   
}    
void print()  
{  
	int i, j;

for(i=0; i<n; i++)  
	{  
		printf("%d",prince[i].n);  
		qsort(prince[i].marry, prince[i].n, sizeof(int),  intcmp);  
		for(j=0; j<prince[i].n; j++)  
		{  
			if(prince[i].marry[j] != prince[i].marry[j+1])  
				printf(" %d",prince[i].marry[j]);  
		}  
		printf("\n");  
	}

}  
int is_married(int girl, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		if(married_girl[i]==girl)
			return 1;
	}
	return 0;
}
void insert()
{
	int i, j, flag;
	for(i=0; i<n; i++)
	{
		for(j=0, flag=1; prince[i].marry[j]; j++)
		{
			if(prince[i].marry[j]==married_girl[i])
			{
				flag=0;
				break;
			}
		}
		if(flag==1)
		{
			prince[i].marry[prince[i].n++]=married_girl[i];
		}
	}
}

void back(int num)
{
	int i;

if(num==n)
	{
		insert();
		return;
	}

for(i=0; prince[num].love[i]; i++)
	{
		if(is_married(prince[num].love[i], num)==0)
		{
			married_girl[num]=prince[num].love[i];
			back(num+1);
		}
	}
}
main()  
{  
	int i;
	input();

for(i=0; prince[0].love[i]; i++)
	{
		married_girl[0]=prince[0].love[i];
		back(1);
		memset(married_girl, 0, sizeof(int)*n);
	}

print();  
}

WA는 피했지만

백트래킹 TLE;;;