개요
그래프 색칠(Graph Coloring)은 인접한 두 정점이 서로 같은 색을 갖지 않도록 그래프의 모든 정점에 색을 할당하는 고전적인 알고리즘 문제입니다. 이 글에서는 가장 널리 쓰이는 해결 방식인 탐욕(Greedy) 색칠 알고리즘을 C++로 구현하는 방법을 단계별로 살펴봅니다.
탐욕 색칠은 정점을 순서대로 하나씩 처리하면서, 이미 색칠된 인접 정점들이 사용 중이지 않은 가장 작은 번호의 색을 배정하는 방식으로 동작합니다. 모든 경우에 최소 색상 수를 보장하지는 않지만, 구현이 간단하고 실행 속도가 빨라 실무에서 폭넓게 활용됩니다.
알고리즘 동작 순서
탐욕 색칠 알고리즘은 아래와 같은 흐름으로 진행됩니다.
- 정점의 개수와 간선의 개수를 입력받습니다.
- greedyColoring() 함수가 각 정점에 색을 할당합니다.
- 첫 번째 정점에 첫 번째 색(색 번호 0)을 할당합니다.
- 나머지 정점들의 색을 -1(아직 미할당 상태)로 초기화합니다.
- 현재 사용 가능한 색을 표시하기 위한 임시 배열(
unuse)을 선언하고 초기화합니다. - 나머지 정점을 차례대로 검사하며, 인접 정점이 이미 사용 중인 색을 제외한 뒤 남은 가장 작은 색을 배정합니다.
- 모든 정점의 최종 색칠 결과를 출력합니다.
예제 코드
아래는 위 알고리즘을 그대로 구현한 C++ 전체 소스 코드입니다.
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n,e,i,j;
vector<vector<int> > g;
vector<int> col;
bool visit[1001];
void greedyColoring()
{
col[0] = 0;
for (i=1;i<n;i++)
col[i] = -1;
bool unuse[n];
for (i=0;i<n;i++)
unuse[i]=0;
for (i = 1; i < n; i++)
{
for (j=0;j<g[i].size();j++)
if (col[g[i][j]] != -1)
unuse[col[g[i][j]]] = true;
int cr;
for (cr=0;cr<n;cr++)
if (unuse[cr] == false)
break;
col[i] = cr;
for (j=0;j<g[i].size();j++)
if (col[g[i][j]] != -1)
unuse[col[g[i][j]]] = false;
}
}
int main()
{
int a,b;
cout<<"Enter number of vertices and edges respectively:";
cin>>n>>e;
cout<<"\n";
g.resize(n);
col.resize(n);
memset(visit,0,sizeof(visit));
for(i=0;i<e;i++)
{
cout<<"\nEnter edge vertices of edge "<<i+1<<" :";
cin>>a>>b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
greedyColoring();
for(i=0;i<n;i++)
{
cout<<"Vertex "<<i+1<<" is coloured with "<<col[i]+1<<"\n";
}
}실행 결과
정점 7개, 간선 6개를 가진 그래프를 입력했을 때의 실행 결과는 다음과 같습니다.
Enter number of vertices and edges respectively:7 6 Enter edge vertices of edge 1 :4 5 Enter edge vertices of edge 2 :2 3 Enter edge vertices of edge 3 :1 1 Enter edge vertices of edge 4 :1 4 Enter edge vertices of edge 5 :6 7 Enter edge vertices of edge 6 :2 2 Vertex 1 is coloured with 1 Vertex 2 is coloured with 1 Vertex 3 is coloured with 2 Vertex 4 is coloured with 2 Vertex 5 is coloured with 1 Vertex 6 is coloured with 1 Vertex 7 is coloured with 2
핵심 포인트 정리
- 시간 복잡도: 각 정점마다 인접 정점을 확인하고 사용 가능한 색을 찾으므로, 인접 리스트 기준으로 약 O(V² + E)의 시간이 걸립니다.
- 공간 복잡도: 색 정보를 저장하는 배열과 사용 가능 여부를 표시하는 임시 배열로 O(V)의 추가 공간이 필요합니다.
- 주의 사항: 탐욕 색칠의 결과는 정점을 처리하는 순서에 따라 달라질 수 있으며, 항상 최소 색상 수(크로매틱 수)를 보장하지는 않습니다.
이처럼 탐욕 색칠 알고리즘은 시간표 작성, 지도 색칠, 레지스터 할당 등 다양한 분야에서 응용되는 기본적이면서도 실용적인 그래프 알고리즘입니다.