그래프 색칠(Graph Coloring) 문제는 그래프 라벨링(Graph Labeling)의 특수한 경우입니다. 이 문제는 그래프의 각 노드(정점)에 색을 하나씩 할당하는 작업으로, 중요한 제약 조건이 있습니다. 바로 인접한 두 정점에는 절대 같은 색을 사용할 수 없다는 것입니다.
이러한 조건을 만족하면서 모든 정점에 색을 칠하는 것이 그래프 색칠 문제의 핵심입니다.
그래프 색칠 문제란?
그래프 색칠은 지도 채색, 시간표 작성, 레지스터 할당 등 다양한 실무 문제로 확장될 수 있는 대표적인 그래프 이론 주제입니다. 예를 들어, 지도에서 국경을 맞대고 있는 나라끼리 서로 다른 색으로 칠해야 하는 상황을 생각하면 이해가 쉽습니다.
이 문제를 해결할 때 일반적으로 탐욕(Greedy) 알고리즘을 사용합니다. 탐욕 알고리즘은 각 정점을 순서대로 방문하면서, 해당 정점에 사용 가능한 첫 번째 색을 즉시 할당하는 방식입니다. 다만 이 방법은 구현이 간단하고 빠르지만, 항상 최소 개수의 색을 사용한다는 보장은 없다는 점에 유의해야 합니다.
입력과 출력
그래프는 인접 행렬(Adjacency Matrix) 형태로 입력받으며, 값이 1이면 두 정점이 연결되어 있음을 의미합니다.
Input: Adjacency matrix of the graph. 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 Output: Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
출력 결과를 보면, 연결되어 있지 않은 정점 0과 1은 같은 색(0번)을 공유하고, 인접한 정점들에는 서로 다른 색이 할당된 것을 확인할 수 있습니다.
알고리즘 동작 원리
graphColoring(graph)
입력 − 색칠할 대상 그래프
출력 − 각 정점에 할당된 색 정보
알고리즘의 전체 흐름은 다음과 같습니다.
Begin
declare a list of colors
initially set the color 0 for first node
define an array colorUsed to track which color is used, and which colors have never used.
for all vertices i except first one, do
mark i as unassigned to any color
done
mark colorUsed to false for all vertices
for all vertices u in the graph except 1st vertex, do
for all vertex v adjacent with u, do
if color[v] is unassigned, then
mark colorUsed[color[v]] := true
done
for all colors col in the color list, do
if color is not used, then
stop the loop
done
color[u] := col
for each vertex v which is adjacent with u, do
if color[v] is unassigned, then
colorUsed[color[v]] := false
done
done
for all vertices u in the graph, do
display the node and its color
done
End핵심 아이디어를 단계별로 정리하면 다음과 같습니다.
- 첫 번째 정점에는 무조건 0번 색을 할당합니다.
- 나머지 정점들은 아직 색이 배정되지 않은 상태(-1)로 초기화합니다.
- 각 정점 u를 처리할 때, u와 인접한 정점들이 이미 사용 중인 색을 colorUsed 배열에 표시하여 사용 불가능하게 만듭니다.
- 사용 가능한 첫 번째 색을 찾아 정점 u에 할당합니다.
- 다음 정점을 처리하기 전에 colorUsed 배열을 초기화하여 재사용할 수 있도록 합니다.
C++ 구현 예제
위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.
#include<iostream>
#define NODE 6
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void graphColoring() {
int color[NODE];
color[0] = 0; //첫 번째 노드에 첫 번째 색 할당
bool colorUsed[NODE]; //색의 사용 여부를 확인하는 배열
for(int i = 1; i<NODE; i++)
color[i] = -1; //나머지 정점은 미배정 상태로 초기화
for(int i = 0; i<NODE; i++)
colorUsed[i] = false; //초기에는 어떤 색도 선택되지 않음
for(int u = 1; u<NODE; u++) { //나머지 NODE-1개 정점 처리
for(int v = 0; v<NODE; v++) {
if(graph[u][v]){
if(color[v] != -1) //이미 색이 할당된 경우 사용 불가 처리
colorUsed[color[v]] = true;
}
}
int col;
for(col = 0; col<NODE; col++)
if(!colorUsed[col]) //아직 사용되지 않은 색 탐색
break;
color[u] = col; //찾은 색을 해당 정점에 할당
for(int v = 0; v<NODE; v++) { //다음 반복을 위해 사용 여부 초기화
if(graph[u][v]) {
if(color[v] != -1)
colorUsed[color[v]] = false;
}
}
}
for(int u = 0; u<NODE; u++)
cout <<"Color: " << u << ", Assigned with Color: " <<color[u] <<endl;
}
main() {
graphColoring();
}실행 결과
Node: 0, Assigned with Color: 0 Node: 1, Assigned with Color: 0 Node: 2, Assigned with Color: 1 Node: 3, Assigned with Color: 2 Node: 4, Assigned with Color: 1
마치며
그래프 색칠 문제는 탐욕 알고리즘만으로도 손쉽게 해결할 수 있지만, 최적해(최소 색 개수)를 보장하지 않는다는 한계가 있습니다. 최소 색 개수를 반드시 구해야 하는 경우에는 백트래킹(Backtracking) 기법을 활용한 정확한 해법을 고려해야 합니다. 또한 그래프 색칠은 NP-완전 문제에 속하기 때문에, 정점 수가 많아질수록 계산 비용이 급격히 증가한다는 점도 기억해두면 좋습니다.