[백준] 12946번 - 육각 보드 / C++

문제

크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다.

육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.

어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄부터 N개의 줄에는 어떤 칸을 색칠해야 하는지에 대한 정보가 주어진다.

i번째 줄의 j번째 문자는 (i, j) 칸의 정보를 나타내고, '-'인 경우는 색칠하지 않는 것이고 'X'면 색칠해야 하는 것이다.

 

출력

첫째 줄에 필요한 색의 종류의 최솟값을 출력한다. 

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int color;
char selected[50][50];
int colored[50][50];
int dy[] = {-1, -1, 0, 0, 1, 1};
int dx[] = {0, 1, -1, 1, -1, 0};

void coloring(int i, int j, int c)
{
	int k;
	int ny;
	int nx;

	colored[i][j] = c + 1;
	color = max(color, 1);
	for (k = 0; k < 6; k++)
	{
		ny = i + dy[k];
		nx = j + dx[k];
		if (!(ny >= 0 && ny < N && nx >= 0 && nx < N))
			continue;
		if (selected[ny][nx] == '-')
			continue;
		if (colored[ny][nx] == 0)
			coloring(ny, nx, 1 - c);
		color = max(color, 2);
		if (colored[ny][nx] == c + 1)
			color = max(color, 3);
	}
}

int main(void)
{
	int i;
	int j;
	string line;

	cin >> N;
	if (N < 1 || N > 50)
	{
		return -1;
	}	
	for (i = 0; i < N; i++)
	{
		cin >> line;
		for (j = 0; j < N; j++)
			selected[i][j] = line[j];
		line.clear();
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			if (selected[i][j] == 'X' && colored[i][j] == 0)
				coloring(i, j, 0);
		}
	}
	cout << color << endl;
	return 0;
}

 

링크

12946번: 육각 보드

inbdni/Baekjoon