아무리봐도 비효율적이다..
주어진 조건에서 바로 순열을 만들 수 있으면 훨씬 빠를텐데...
/*
Subject: #124 Following Orders
e-mail: morcavon@gmail.com
Homepage: http://morcavon.byus.net
Building: 14/02/2005 ~ 15/02/2005
Last Update: 15/02/2005
*/
/*
<INPUT>
A list of variables
A list of contraints (given by a pair of variables, where 'x', 'y' indicate that x < y)
-
<OUTPUT>
All ordering consistent with the constraints.
(orderings are printed lexicographical order, one per line)
-
<CONDITION>
All variables are single character, lower-case letters.
2 <= # of var <= 20
1 <= # of const <= 50
1 <= # of orderings <= 300
Input is terminated by EOF
-
*/
#include <iostream>
#include <string.h>
#include <stdlib.h> // qsort()
using namespace std;
struct Table
{
char value;
struct Table *link;
};
void perm(char *var, const int k, const int n);
void sort(char *var, int n);
void create_constraint(Table *tab);
void clear(void);
int is_consistent(char *var, int n);
int is_there(char *s, char ch, int n);
int cmp(const void *s1, const void *s2);
Table tab[27] = {0}; // 각 알파벳을 헤드로 갖는 리스트를 만들꼬다..
char result[301][21];
int idx = 0; // index for result array
int main()
{
int n; // # of variables
char var[21]; // include NULL
while (1) {
// input sorting
for (n = 0; cin >> var[n]; ) {
n++;
if (cin.get() == '\n')
break;
}
sort(var, n);
// 조건들을 읽음
create_constraint(tab);
// 순열을 만들면서 각각의 결과가 조건에 맞는지 검사하여 결과값들을 구한다.
perm(var, 0, n);
// result sorting alphabetical (이거 땜에 엉뚱한 곳에서 고생했다!!=_=)
qsort(result[0], idx, sizeof(result[0]), cmp);
// print
for (n = 0; n < idx; n++)
cout << result[n] << endl;
// prepare next input
clear();
if (cin.eof() == true)
break;
cout << "\n";
}
return 0;
}
void perm(char *var, const int k, const int n)
{
// var[k] ~ var[n-1]에 대한 순열 생성.
int i;
if (k == n - 1) {
// 하나의 순열을 찾아냈다!@_@ 주어진 조건과 비교해서 맞으면 출력
if (is_consistent(var, n)) {
var[n] = '\0';
strcpy(result[idx++], var);
}
}
else {
for (i = k; i < n; i++) {
// var[k]와 var[i]를 교환
char temp = var[k]; var[k] = var[i]; var[i] = temp;
perm(var, k + 1, n);
// 복원
temp = var[k]; var[k] = var[i]; var[i] = temp;
}
}
}
void sort(char *var, int n)
{
// 입력된 변수 배열을 정렬.(내림차순)
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (var[j] < var[i]) {
char temp = var[j]; var[j] = var[i]; var[i] = temp;
}
}
}
}
void create_constraint(Table *tab)
{
// 조건들을 읽어 해당 tab에 연결한다.
char x, y;
Table *w_ptr;
for (; cin >> x >> y; ) {
Table *new_node = new Table;
new_node->value = y;
new_node->link = NULL;
// 삽입 할 위치 선정
for (w_ptr = &tab[x - 'a']; w_ptr->link != NULL; w_ptr = w_ptr->link)
;
w_ptr->link = new_node;
if (cin.get() == '\n')
break;
}
}
void clear(void)
{
int i;
Table *w_ptr;
for (i = 0; i < 26; i++) {
if (tab[i].link == NULL)
continue;
Table *temp;
for (w_ptr = tab[i].link; w_ptr != NULL; w_ptr = temp) {
temp = w_ptr->link;
delete w_ptr;
}
tab[i].link = NULL;
}
idx = 0;
}
int is_consistent(char *var, int n)
{
// 주어진 순열 var가 조건에 맞는지 검사한다.
for (int i = 1; i < n; i++) {
for (Table *w_ptr = tab[var[i] - 'a'].link; w_ptr != NULL; w_ptr = w_ptr->link) {
if (is_there(var, w_ptr->value, i))
return 0;
}
}
return 1;
}
int is_there(char *s, char ch, int n)
{
// 길이가 n인 문자열 s에 ch가 있는지 없는지 알아봄...
for (; n > 0 && *s != ch; s++, n--)
;
if (n == 0)
return 0;
else
return 1;
}
int cmp(const void *s1, const void *s2)
{
return strcmp((char*)s1, (const char*)s2);
}
