되추적 알고리즘 (graph coloring)

어휴 .. 다른 곳은 너무 어렵게 설명이 나와있네..

 

graph coloring 알고리즘

 

문제 설명 

인접한 지역이 같은 색이 되지 않도록 지도를 색칠하는 것 

 

입력 : n - node의 수

m - 색깔의 수

w [i][j] - 비 방향 그래프를 나타냄

초기 호출 = graph_coloring(0)

 

 

int w1[MAX][MAX] = {
    {0, 1, 1, 1},
    {1, 0, 1, 0},
    {1, 1, 0, 1},
    {1, 0, 1, 0}

};

 

bool promising_1(int i) {
    int j = 1;
    bool sw = true;
    while (j < i && sw) {
        if (w1[i][j] && vcolor[i] == vcolor[j])  // 인접하고 색이 같은지 여부 조사
            sw = false;
        j++;
    }
    return sw;
}

void graph_coloring(int i) {
    int color;
    if (promising_1(i)) {
        if (i == n1) { // 마지막 노드까지 갔을 때 결과 출력 
            for (int a = 0; a < n1; a++)
                cout << vcolor[a];
            exit(1);
        }
        else {
            for (color = 1; color <= m; color++) {
                vcolor[i + 1] = color;  // 다음 노드ㅔㅇ 모든 색을 시도해 본다.
                graph_coloring(i + 1);
            }
        }
    }
}

void main() {
    n1 = 4;
    m = 3;
    graph_coloring(0);
    node = 5; 

}

결과는 ??

연결되어 있는 노드들의 숫자를 잘 바꿔준 것을 확인 할 수 있다. 

오랫만에 c언어를 사용하니깐 조금 .. 그렇다