M-착색 문제(M-Coloring Problem): 백트래킹으로 푸는 그래프 색칠 알고리즘

그래프 이론에서 M-착색 문제(M-Coloring Problem)는 하나의 무방향 그래프와 m가지 색이 주어졌을 때, 서로 인접한 두 정점이 같은 색을 갖지 않도록 모든 정점에 색을 배정할 수 있는지 판별하는 문제입니다. 해가 존재한다면 어떤 정점에 어떤 색이 배정되었는지도 함께 출력해야 합니다.

이 문제는 대표적인 백트래킹(Backtracking) 기법으로 해결합니다. 0번 정점부터 시작해 한 정점씩 차례대로 색을 시도하는데, 색을 배정하기 전에는 반드시 해당 색이 안전한지 확인해야 합니다. 인접한 정점 중 이미 같은 색을 사용하고 있다면 그 색은 안전하지 않으므로, 다른 색을 시도하거나 이전 단계로 되돌아가야 합니다.

입력과 출력

입력:
그래프 G(V, E)의 인접 행렬과 사용할 수 있는 최대 색의 개수를 나타내는 정수 m


예를 들어 최대 색의 개수 m = 3이라고 가정합니다.
출력:
알고리즘은 각 노드에 배정된 색을 반환합니다. 해가 존재하지 않으면 false를 반환합니다.

위 입력에 대한 색 배정 결과:
노드 0 → 색 1
노드 1 → 색 2
노드 2 → 색 3
노드 3 → 색 2

알고리즘

isValid(vertex, colorList, col)

입력 − 검사할 정점(vertex), 현재까지의 색 목록(colorList), 배정하려는 색(col)

출력 − 해당 색의 배정이 유효하면 true, 그렇지 않으면 false

Begin
    for all vertices i of the graph, do
        if there is an edge between vertex and i, and col = colorList[i], then
            return false
    done
    return true
End

그래프의 모든 정점을 순회하면서, 현재 정점과 간선으로 연결된 정점이 이미 같은 색을 사용하고 있는지 검사합니다. 하나라도 발견되면 즉시 false를 반환합니다.

graphColoring(colors, colorList, vertex)

입력 − 사용 가능한 최대 색의 수(colors), 각 정점의 색 정보를 담은 목록(colorList), 처리할 시작 정점(vertex)

출력 − 모든 정점에 색을 성공적으로 배정하면 true, 실패하면 false

Begin
    if all vertices are checked, then
        return true
    for all colors col from available colors, do
        if isValid(vertex, colorList, col), then
            add col to the colorList for vertex
            if graphColoring(colors, colorList, vertex+1) = true, then
                return true
            remove color for vertex
    done
    return false
End

모든 정점을 처리했다면 true를 반환해 재귀를 종료합니다. 그렇지 않으면 사용 가능한 색을 하나씩 시도해 보고, 유효한 색이라면 일단 배정한 뒤 다음 정점으로 재귀 호출을 진행합니다. 이후 단계에서 해를 찾지 못하면 방금 배정한 색을 제거하고(백트래킹) 다른 색을 시도합니다. 모든 색이 실패하면 false를 반환합니다.

C++ 구현 예제

#include<iostream>
#define V 4
using namespace std;

bool graph[V][V] = {
    {0, 1, 1, 1},
    {1, 0, 1, 0},
    {1, 1, 0, 1},
    {1, 0, 1, 0},
};

void showColors(int color[]) {
    cout << "Assigned Colors are: " <<endl;
    for (int i = 0; i < V; i++)
        cout << color[i] << " ";
    cout << endl;
}

bool isValid(int v,int color[], int c) {     //check whether putting a color valid for v
    for (int i = 0; i < V; i++)
        if (graph[v][i] && c == color[i])
            return false;
    return true;
}

bool graphColoring(int colors, int color[], int vertex) {
    if (vertex == V)     //when all vertices are considered
        return true;

    for (int col = 1; col <= colors; col++) {
        if (isValid(vertex,color, col)) {     //check whether color col is valid or not
            color[vertex] = col;
            if (graphColoring (colors, color, vertex+1) == true)     //go for additional vertices
                return true;

            color[vertex] = 0;
        }
    }
    return false; //when no colors can be assigned
}

bool checkSolution(int m) {
    int *color = new int[V];     //make color matrix for each vertex

    for (int i = 0; i < V; i++)
        color[i] = 0;         //initially set to 0

    if (graphColoring(m, color, 0) == false) {     //for vertex 0 check graph coloring
        cout << "Solution does not exist.";
        return false;
    }
    showColors(color);
    return true;
}

int main() {
    int colors = 3;          // Number of colors
    checkSolution (colors);
}

실행 결과

Assigned Colors are:
1 2 3 2

실행 결과를 보면 0번 정점은 색 1, 1번 정점은 색 2, 2번 정점은 색 3, 3번 정점은 색 2가 배정되어, 인접한 정점끼리 서로 다른 색을 갖는 것을 확인할 수 있습니다.

M-착색 문제의 시간 복잡도는 최악의 경우 각 정점마다 m가지 색을 모두 시도하므로 O(m^V)입니다. 실제로 이 문제는 NP-완전 문제에 속하기 때문에, 정점의 수가 커질수록 탐색 시간이 지수적으로 증가할 수 있다는 점을 유의해야 합니다.