PKU 1904. King's Quest. TLE

#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;;;