PKU 1904. King's Quest. WA

지환태 2009. 1. 19. 14:44

그냥 모든 경우의 수를 탐색하는 방법입니다.

#include <stdio.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",&prince[i].marry[prince[i].n++]);
	}
}

int is_married(int num, int girl)
{
	int i;

for(i=0; prince[num].marry[i]; i++)
	{
		if(prince[num].marry[i] == girl)
			return 1;
	}
	return 0;
}

int back(int num)
{
	int i;
	if(num==n)
		return 0;
	for(i=0; prince[num].love[i]; i++)
	{
		if(married_girl[prince[num].love[i]]==0 && is_married(num, prince[num].love[i])==0)
		{
			prince[num].marry[prince[num].n++]=prince[num].love[i];
			married_girl[prince[num].love[i]]=1;
		}
		else continue;

back(num+1);
		if(num==0)
			memset(married_girl,0,sizeof(int)*n);

}
	return 0;
}

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");
	}

}

main()
{
	input();
	back(0);
	print();
}

문제 번역한 걸 못알아먹어서 어찌해야할 지를 모르겠네요 ㅇㅅㅇ;;