육각보드

문제

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

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

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

입력

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

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

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

출력

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

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#include<map>
#include<cstring>
using namespace std;

int n;
int dx[] = { 0,0,-1,1,-1,1 };
int dy[] = { 1,-1,0,0 ,1,-1};



int main() {

	char arr[51][51];
	int check[51][51];
	queue<pair<int,int> >q;
	bool ans = false;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	memset(check, 0, sizeof(check));

	for(int k=0; k<n; k++){
		for (int t = 0; t < n; t++) {
			if (arr[k][t] == 'X'&&check[k][t] == 0) {
				q.push(make_pair(k, t));
				int num = 1;
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
				//	cout << "x:" << x << "y:" << y << endl;
					q.pop();
					if (arr[x][y] == 'X' && check[x][y] == 0) {
						map<int, bool>m;
						for (int i = 0; i < 6; i++) {

							int nx = x + dx[i];
							int ny = y + dy[i];
							if (nx >= 0 && nx < n && ny >= 0 && ny < n) {

								if (arr[nx][ny] == 'X') {
									if (check[nx][ny] == 0) {
										q.push(make_pair(nx, ny));
									}
									else {
										m[check[nx][ny]] = true;
									}
								}
							}
						}
						while (m[num] == true) {
							num++;
						}
						if (num == 3) { ans = true; break; } //3이되는 순간 최대는 3이됨 
						check[x][y] = num;
						num = 1;
						m.clear();
					}
				}
			}
			if (ans == true) { break; }
		}
	}

	if (ans == true) { cout << 3 << endl; return 0; }
	int max = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (max < check[i][j]) { max = check[i][j]; }
		}
	}
	cout << max<<endl;
	return 0;
	}

	

 

어떤알고리즘? 어떤 논리로?

- BFS로 풀었다. 그 이유는 6방향의 색을 확인하면서 색을 골라야 하고 6방향중에 색칠해야 하는 부분이면서 아직 칠하지 않은 것은 큐에 넣어 참조를 하게 만들었다. 색은 숫자로 표현해서 check에 저장. 색1 부터 돌면서 이미 칠해진 색이면 색2를 고름. 이렇게 6방향 중에 안칠한 색을 골라서 칠하도록 만들었다. 

- 하지만 여기서 답을 check에 있는 값중에 최대값을 갖는 색을 고르게 되면 문제가 생긴다. 위의 6각보드는 최대 3개로 충분히 다 칠할 수 있는데 만약 이를 고려하지 않고 그냥 bfs 를 이용해서 구하면 3을 넘는 경우가 발생한다. 그래서 무조건 3이라는 색이 발생하면 3을 리턴하도록 만드니까 바로 통과가 됐다.

- 왜 3이 최대고 그냥 bfs로 구하면 3이 넘는경우가 발생하는지는 이유는 알지만 설명하기 귀찮음으로 패스