1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <fstream>
 
using namespace std;
int case_count = 0;
int** adjacent_arr;
char line[64];
int node_size;
int* vertex_color_arr;
int* case_list;
int result = 0;
 
void initArray();
void Swap(int& case_list1, int& case_list2);
void Permutation(int depth);
int testNode(int node);
int searchNodeColor(int node);
void showVertexColor();
 
int main(void)
{
    initArray();
    Permutation(0);
 
    cout << "Failed Case" << endl;
    abort();
 
    return 0;
}
 
void initArray()
{
    ifstream ifs("./input/graph10_yes.dat", ios::binary);
 
    if (ifs.is_open() == false)
        cout << "File Open Failed" << endl;
 
    ifs.getline(line, 64);
    node_size = atoi(line);
 
    case_list = new int[node_size];
    for (int i = 0; i < node_size; i++)
        case_list[i] = i;
 
    adjacent_arr = new int*[node_size];
    for (int i = 0; i < node_size; i++)
        adjacent_arr[i] = new int[node_size];
 
    for (int i = 0; i < node_size; i++)
        for (int j = 0; j < node_size; j++)
            adjacent_arr[i][j] = -1;
 
    vertex_color_arr = new int[node_size];
    for (int i = 0; i < node_size; i++)
        vertex_color_arr[i] = -1;
 
    while (ifs.getline(line, 64))
    {
        char* pch = strtok(line, "<");
        int node = atoi(pch) - 1;
        while (true)
        {
            pch = strtok(NULL, "> ");
            if (pch == nullptr)
                break;
 
            int adjacent_node = atoi(pch) - 1;
            adjacent_arr[node][adjacent_node] = 1;
            adjacent_arr[adjacent_node][node] = 1;
        }
    }
}
 
void Swap(int& case_list1, int& case_list2)
{
    int temp = case_list1;
    case_list1 = case_list2;
    case_list2 = temp;
}
 
// 탐색할 수 있는 모든 경우의 수를 구합니다
// node_size가 5라면, {0,1,2,3,4}의 Permutation이 됩니다.
// 구한 경우의 수 마다 색을 지닐 수 있는지 검사합니다.
void Permutation(int depth)
{
    int result = 0;
    
    if (depth == node_size)
    {
        //cout << "Count of Case :" << ++case_count << endl;
 
        for (int i = 0; i < node_size; i++)
            result +=testNode(case_list[i]);    
        
        if (result >-1)
        {
            showVertexColor();
            exit(0);
        }
        
        for (int i = 0; i < node_size; i++)
            vertex_color_arr[i] = -1;
        
        return;
    }
    else
    {
        for (int i = depth; i < node_size; i++)
        {
            Swap(case_list[i], case_list[depth]);
            Permutation(depth + 1);
            Swap(case_list[i], case_list[depth]);
        }
    }
}
 
//노드 주위에 색이 꽉 찼다면 -1을 반환합니다.
int testNode(int node)
{
    for (int i = 0; i < node_size; i++)
    {
        if (adjacent_arr[node][i] == 1)
        {
            int color = searchNodeColor(node);
            if (color == -1)
                return -1;
            else
                vertex_color_arr[node] = color;
 
            return 0;
        }
    }
}
//주어진 노드를 보고 주위에 색이 꽉 찼는지 검사합니다.
int searchNodeColor(int node)
{
    int rgb[3] = { 1,2,3 };
    for (int i = 0; i < node_size; i++)
    {
        if (adjacent_arr[node][i] == 1)
        {
            int color = vertex_color_arr[i];
            if (color != -1)
                rgb[color - 1] = -1;
        }
    }
 
    for (int i = 0; i < 3; i++)
        if (rgb[i] != -1)
            return rgb[i];
    
    return -1;
}
 
void showVertexColor()
{
    for (int i = 0; i < node_size; i++)
    {
        cout << "V" << i << " : ";
        
        switch (vertex_color_arr[i])
        {
        case 1:
            cout << "R";
            break;
        case 2:
            cout << "G";
            break;
        case 3:
            cout << "B";
            break;
        }
        cout << endl;
    }
}
cs




완전 탐색을 하기 위해서 순열을 이용한 결과...

케이스가 5라면 5!, 케이스가 10개라면 10! 케이스가 15개라면 15!을 탐색해야 합니다.

실패를 하려면 5!,10!,15!의 모든 경우가 실패여야 실패이고

성공 하려면 한 번이라도 성공하면 성공인 것이지요

실패가 너무 오래걸리는데.. 케이스를 줄이려면 어찌해야할까요?