12946번 육각 보드

이번 문제에서 공부할 것은 다음과 같다.
1) 이분 그래프를 활용한다. 여태 제대로 배운적이 없다. 이분 그래프는 BFS, DFS둘다 이용할 수 있지만, DFS를 사용하려고 한다. 시작 노드를 RED로 하고, 시작 노드와 연결된 다음 노드는 BLUE로 지정한다. 그 다음 연결된 노드는 RED... 이렇게 반복한다.
2) memeset에 대해서도 제대로 배운적이 없었다. 하나의 값만 받는 것이 아니라, 여러개의 입력을 반복해서 받을때, 초기화하는 목적으로 사용한다. 여기선 한번만 받는데 그냥 귀찮아서 memset을 사용했다.

문제 뜯어보기

육각보드는 최대 3가지 색으로 모두 칠할 수 있다. 따라서 답은 0,1,2,3중에 하나이다. 칠할게 하나도 없으면 0, 칠해야 하는 면들이 서로 마주보지 않으면 1, 이분 그래프로 해결가능하면 2, 그 이상이면 3이다.

코딩짜기, 구체화

앞에서 말했듯이 DFS를 이용하여 이분 그래프인지 확인한다.

어려웠던 점

처음 문제를 정확히 뜯어봐야겠다. 답이 0~3인지 생각도 못했다🤦‍♂️.

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int n;
int color[50][50];
int dx[6] = { -1,-1,0,1, 1, 0 };
int dy[6] = { 0,  1,1,0,-1,-1 };
int ans = 0;
vector<string> a;
void DFS(int x, int y, int c) {
	color[x][y] = c; // c색깔로 색칠하였다.
	ans = max(ans, 1);
	for (int i = 0; i < 6; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx >= n || xx<0 || yy>=n || yy < 0) continue;
		if (a[xx][yy] == 'X') {//칠해야 하는데
			if (color[xx][yy] == -1) DFS(xx, yy, 1 - c); // 아직 칠하지 않은 경우, 1-c로 칠해줌 0->1->0->1...로 돌아가게
			ans = max(ans, 2);
			if (color[xx][yy] == c) ans = max(ans, 3);
		}
	}
}
int main() {
	cin >> n;
	
	a.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	memset(color, -1, sizeof(color));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (a[i][j] == 'X' && color[i][j] == -1) DFS(i, j, 0); //색칠해야 하는데, 아직 색칠하지 않은 경우
		}
	}
	cout << ans << '\n';
	return 0;
}