Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 4색 문제(그래프 색칠) 프로그램

이 글에서는 그래프 이론의 유명한 문제인 4색 문제(Graph Coloring Problem)를 백트래킹(backtracking) 기법으로 해결하는 C++ 프로그램을 소개합니다. 4색 문제란 지도 위의 인접한 영역에 서로 다른 색을 칠할 때 최대 4가지 색만으로 충분하다는 정리에 기반한 문제로, 그래프의 모든 정점을 인접한 정점끼리는 서로 다른 색이 되도록 칠하는 것을 목표로 합니다.

알고리즘

이 알고리즘은 크게 세 가지 함수로 구성됩니다.

1. issafe() 함수

현재 정점 v에 특정 색상을 배정해도 안전한지 검사하는 함수입니다. 먼저 해당 정점과 간선으로 연결된 인접 정점이 존재하는지 확인하고, 존재한다면 새로 칠하려는 색이 이미 인접 정점에서 사용 중인지 검사합니다. 사용 중이라면 false를 반환하여 해당 색을 배정할 수 없음을 알립니다.

2. graphColoringtil() 함수

백트래킹 방식으로 4색 칠하기 문제를 실제로 해결하는 핵심 재귀 함수입니다.

  • g[V][V]: 그래프의 정점 개수 V를 가지는 2차원 배열(인접 행렬)
  • m: 사용할 수 있는 최대 색상 수
  • col[]: 각 정점에 배정된 색상 번호(1부터 m까지)를 저장하는 배열

동작 순서는 다음과 같습니다.

시작
    모든 정점에 색이 배정되었다면(v == V) true 반환
    c = 1부터 m까지 반복:
        isSafe(v, g, col, c)가 참이면
            col[v] = c 로 색 배정
            graphColoringtil(g, k, col, v+1)을 재귀 호출하여
            나머지 정점에도 색 배정 시도
            성공하면 true 반환
            실패하면 col[v] = 0 으로 되돌림(백트래킹)
    가능한 색이 없으면 false 반환
끝

3. graphColor() 함수

내부적으로 graphColoringtil()을 호출하여 문제를 해결하는 래퍼(wrapper) 함수입니다. m개의 색으로 색칠이 불가능하면 false를 반환하고, 가능하면 true를 반환하며 결과를 출력합니다.

예제 코드

#include <iostream>
#include <cstdio>
#define V 5
using namespace std;

// 정점 v에 색 C를 배정해도 안전한지 검사
bool isSafe(int v, bool graph[V][V], int col[], int C) {
    for (int i = 0; i < V; i++)
        if (graph[v][i] && C == col[i])
            return false;
    return true;
}

// 백트래킹으로 색칠 문제를 해결하는 재귀 함수
bool graphColoringtil(bool g[V][V], int k, int col[], int v) {
    if (v == V) // 모든 정점에 색이 배정된 경우
        return true;
    for (int c = 1; c <= k; c++) { // 정점 v에 여러 색을 시도
        if (isSafe(v, g, col, c)) { // 색 c 배정이 가능한지 확인
            col[v] = c;
            // 나머지 정점에 대한 색 배정을 재귀적으로 시도
            if (graphColoringtil(g, k, col, v + 1) == true)
                return true;
            col[v] = 0; // 색 c로는 해답이 되지 않으므로 제거(백트래킹)
        }
    }
    return false;
}

// 결과 출력 함수
void solution(int color[]) {
    cout << "배정된 색상은 다음과 같습니다:\n";
    for (int i = 0; i < V; i++)
        cout << color[i] << " ";
    cout << "\n";
}

// 전체 색칠 과정을 관리하는 함수
bool graphColor(bool graph[V][V], int k) {
    int *color = new int[V];
    // 모든 색상 값을 0으로 초기화
    for (int i = 0; i < V; i++)
        color[i] = 0;
    if (graphColoringtil(graph, k, color, 0) == false) {
        cout << "해답이 존재하지 않습니다";
        return false;
    }
    solution(color);
    return true;
}

int main() {
    bool g[V][V] = {
        {0, 0, 1, 0, 1},
        {1, 1, 1, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 1, 0, 0}
    };
    int k = 4; // 사용 가능한 최대 색상 수
    graphColor(g, k);
    return 0;
}

실행 결과

배정된 색상은 다음과 같습니다:
1 2 3 1 1

위 실행 결과에서 볼 수 있듯이, 프로그램은 5개의 정점을 가진 그래프에 대해 4가지 색(1~4)을 사용하여 인접한 정점끼리 서로 겹치지 않도록 성공적으로 색을 배정했습니다. 이처럼 백트래킹 기반의 그래프 색칠 알고리즘은 지도 색칠, 시간표 작성, 레지스터 할당 등 다양한 실무 문제에 응용될 수 있습니다.