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
#include <iostream>
#include <cstdio>
#include <fstream>
#include <time.h>
using namespace std;
 
int** adjacent_arr;
char line[64];
int node_size;
int* case_list;
int color_set[3] = { 1,2,3 };
 
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);
    
    //성공하면exit()로 나가므로,여기까지오면실패
    abort();
    return 0;
}
 
void initArray()
{
    ifstream ifs("./input/graph15_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;
 
    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)
    {
        for (int i = 0; i < node_size; i++)
        {
            result += searchNodeColor(i);
            if (result < 0)
                return;
        }
        if (result >-1)
        {
            showVertexColor();
            exit(0);
        }
        cout << endl;
        cout << endl;
        return;
    }
    else
    {
        for (int i = 0; i < 3; i++)
        {
            Swap(color_set[i], color_set[2]);
            case_list[depth] = color_set[2];
            Permutation(depth +1);
            Swap(color_set[i], color_set[2]);
        }
    }
}
 
//주어진 노드를 보고 주위에 색이 꽉 찼는지 검사합니다.
int searchNodeColor(int node)
{
    int rgb[3] = { 1,2,3 };
    
    int myColor = case_list[node];
 
    for (int i = 0; i < node_size; i++)
    {
        if (adjacent_arr[node][i] == 1)
        {
            if (myColor == case_list[i])
                return -1;
        }
    }
    return 0;
}
 
void showVertexColor()
{
    for (int i = 0; i < node_size; i++)
    {
        cout << "V" << i << " : ";
 
        switch (case_list[i])
        {
        case 1:
            cout << "R";
            break;
        case 2:
            cout << "G";
            break;
        case 3:
            cout << "B";
            break;
        }
        cout << endl;
    }
}
cs


처음에 풀었던 것은 

만약 node수가 5개라면

{0,1,2,3,4}의 5!의 경우의 수를 가지고 색을 하나씩 채워갔는데요.

색을 하나 채우고 다른 노드들과 색의 관계가 어떤지 검사하고

ok면 다음 노드로

fail면 처음 부터 시작했읍니다.


하나라도 성공하면 성공이고,

실패를 알려면 모든 경우의 수에 테스트를 해야했습니다.

이것은 node수가 15개라면 15!이라는 어마어마한 케이스를 다 보므로 상당히 느렸읍니다.




그 다음은 힌트를 가지고 풀었는데요

만약 node수가 5개라면

RRRRR

~~~~

RGBRG

~~~~
BBBBB

이런식으로 이미 색을 칠한 노드들을 구할 수 있어요.

이 색이 칠해진 노드들이 규칙에 맞나 검사를하면 3^n으로 가능합니다.

제가 살펴본 규칙은 노드의 색깔과 겹치는 색깔이 주위 노드에 있다면 fail로 처리했읍니다.

처음에 풀었던 것은 순열을 이용했구요 위에 것은 중복 순열을 이용하여 {r,g,b}이 세 경우에서 n개를 뽑는 것을 사용하였읍니다.


이 경우도 역시

하나라도 성공하면 성공이고,

실패를 알려면 모든 경우의 수에 테스트를 해야했습니다.

하지만 node수에 따라 3^n이 되어 위에 것보다 훨씬 빠릅니다.


휴휴