[알고리즘] 그리디 알고리즘 - 그래프 컬러링

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

그래프 컬러링

개요

　그래프 컬러링(graph coloring) 문제는 주어진 그래프에서 서로 인접한 정점끼리 같은 색을 갖지 않도록 모든 정점에 색상을 지정하는 것이다. 이때 에지의 가중치는 사용하지 않는다. 컬러링의 주요 종류는 다음과 같다.

 

• 정점 컬러링: 가장 기본적인 형태의 그래프 컬러링. 인접한 정점들은 다른 색깔을 가져야 한다는 규칙을 따름.
• 에지 컬러링: 각 에지를 색칠하는 데 중점을 두며, 어떤 두 에지도 같은 색깔을 가질 수 없음. 이 규칙은 에지가 공유하는 정점에도 적용됨.
• 착색수(chromatic number): 그래프를 적절히 색칠하는 데 필요한 최소 색깔 수 (NP-완전 문제)

 

　그래프 컬러링은 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기, 시험 시간표 작성 등을 그래프로 모델링한 후 컬러링 문제 형태로 해결할 수 있다. 그러나 그래프 컬러링에 필요한 최소 개수의 색상 수를 찾는 것은 NP-완전 문제이므로 그 수를 정확하게 계산하는 것은 어렵다. 하지만 문제를 조금 변경함으로써 해결할 수 있다.

---

구현

 

　다음과 같은 그래프가 있다고 해보자. 여기서 인접한 정점끼리 겹치지 않게 색을 정하려면 다음과 같은 과정을 거친다.

 

1. 정점 선택: 시작점으로 정점을 하나 선택
2. 색상 부여: 선택한 정점에 색상을 부여
3. 인접한 정점 검사: 다음 정점을 선택하고, 이 정점이 이전에 색칠한 정점과 인접한 지 확인. 만약 인접하다면, 이전에 색칠한 정점과 다른 색상을 부여
4. 그래프 순회: 이 과정을 그래프의 모든 정점에 대해 반복. 같은 색상을 가진 인접한 정점이 없도록 정점에 색상을 부여
5. 검증: 마지막으로 모든 정점이 색칠되었는지 확인하고, 인접한 정점끼리 같은 색상을 공유하지 않는지 확인

 

　이를 코드로 구현해 보도록 하자.

 

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using us = unsigned;

struct edge
{
	us _src, _dst, _weight;

	bool operator < (const edge& e) const
	{
		return this->_weight < e._weight;
	}

	bool operator > (const edge& e) const
	{
		return this->_weight > e._weight;
	}
};

class graph
{
	us _v;
	std::vector<edge> _list;

public:
	graph(us n) : _v(n) {}

	us vertices() const
	{
		return _v;
	}

	auto& edges() const
	{
		return _list;
	}

	auto edges(us v) const
	{
		std::vector<edge> edge_from_v;

		for (const auto& e : _list)
		{
			if (e._src == v)
				edge_from_v.push_back(e);
		}

		return edge_from_v;
	}

	void add_edge(edge&& e)
	{
		if (e._src >= 1 && e._src <= _v && e._dst >= 1 && e._dst <= _v)
			_list.push_back(e);

		else
			std::cerr << "Invalid range vertex\n";
	}

	friend std::ostream& operator << (std::ostream& os, const graph& g)
	{
		for (us i = 1; i < g.vertices(); ++i)
		{
			auto edges = g.edges(i);

			os << i << ":  ";
			
			for (const auto& e : edges)
				os << "{" << e._dst << ": " << e._weight << "}, ";
			os << "\n";
		}

		return os;
	}
};

　이전 게시글에서 구현했던 에지와 그래프 코드를 가져와 사용하자.

 

enum class Color
{
	RED = 1,
	BLUE,
	GREEN,
	YELLOW,
	BLACK,
	WHITE,
	COLOR_COUNT
};

　색을 표현할 enum 클래스 Color다. Red부터 White까지 1부터 6까지 숫자를 부여하고, COLOR_COUNT를 사용하여 색상의 총 수를 확인하게 하였다.

 

auto coloring(const graph& g)
{
	auto size = g.vertices();
	std::vector<us> assigned_color(size);

	for (us i = 1; i < size; ++i)
	{
		auto outgoing_edge = g.edges(i);
		std::set<us> neighbours;

		for (const auto& e : outgoing_edge)
			neighbours.insert(assigned_color[e._dst]);

		auto smallest = 1;

		for (; smallest <= static_cast<int>(Color::COLOR_COUNT); ++smallest)
		{
			if (neighbours.find(smallest) == neighbours.end())
				break;
		}

		assigned_color[i] = smallest;
	}

	return assigned_color;
}

　그래프 컬러링 알고리즘을 구현한 coloring() 함수다. 1번 정점부터 for문을 통해 차례대로 검사한다. i번째 정점과 인접해 있는 정점들의 현재 색상을 확인한 후에, 칠해지지 않은 색상 중 가장 작은 숫자의 색상 smallest을 선택하는 식으로 구현했다.

 

std::string color_to_string(Color color)
{
	switch (color)
	{
	case Color::RED:
		return "Red";
	case Color::BLUE:
		return "Blue";
	case Color::GREEN:
		return "Green";
	case Color::YELLOW:
		return "Yellow";
	case Color::BLACK:
		return "Black";
	case Color::WHITE:
		return "White";
	default:
		return "Invalid Color";
	}
}

void print_color(std::vector<us>& colors)
{
	for (auto i = 1; i < colors.size(); ++i)
		std::cout << i << ": " << color_to_string(static_cast<Color>(colors[i])) << "\n";
}

void print_color_grouped(std::vector<us>& colors)
{
	std::map<Color, std::vector<us>> color_groups;

	for (us i = 1; i < colors.size(); ++i)
		color_groups[static_cast<Color>(colors[i])].push_back(i);

	for (const auto& color_group : color_groups)
	{
		std::cout << color_to_string(color_group.first) << ": ";
		for (auto v : color_group.second)
			std::cout << v << ", ";
		std::cout << "\n";
	}
}

　print_color(), print_color_grouped() 함수 둘 다 그래프 컬러링 결과를 화면에 출력하는 것이다.

 

int main()
{
	graph g(9);

	std::map<us, std::vector<std::pair<us, us>>> edge_map;

	edge_map[1] = { {2, 0}, {5, 0} };
	edge_map[2] = { {1, 0}, {5, 0}, {4, 0} };
	edge_map[3] = { {4, 0}, {7, 0} };
	edge_map[4] = { {2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0} };
	edge_map[5] = { {1, 0}, {2, 0}, {4, 0}, {8, 0} };
	edge_map[6] = { {4, 0}, {7, 0}, {8, 0} };
	edge_map[7] = { {3, 0}, {6, 0} };
	edge_map[8] = { {4, 0}, {5, 0}, {6, 0} };

	for (const auto& i : edge_map)
	{
		for (const auto& j : i.second)
			g.add_edge(edge{ i.first, j.first, j.second });
	}

	std::cout << "[Input Graph]\n";
	std::cout << g << "\n";

	auto ans = coloring(g);
	std::cout << "[Graph Coloring]\n";
	print_color(ans);
	std::cout << "\n";
	print_color_grouped(ans);
}

출력 결과

　해당 출력에 의해 컬러링 결과는 다음과 같다.

 

---

요약

그래프 컬러링
1. 정의: 주어진 그래프에서 서로 인접한 정점끼리 같은 색을 갖지 않도록 모든 정점에 색상을 지정하는 것
2. 종류
　- 정점 컬러링, 에지 컬러링, 크로마틱 수