풀이
잘 생각해보면 보드는 최대 3개의 색으로 칠할 수 있다. 여기를 참고.
0과 1인 경우는 따로 처리해주고 DFS로 돌면서 이분그래프이면 답은 2, 아니면 3이다.
코드
#include <bits/stdc++.h>
using namespace std;
const int dx[6] = { -1,-1,0,0,1,1 };
const int dy[6] = { 0,1,-1,1,-1,0 };
int n, ans, col[51][51];
char e[51][51];
void dfs(int x, int y, int c) {
col[x][y] = c;
ans = max(ans, 1);
for (int i = 0; i < 6; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (!(0 <= nx && nx < n && 0 <= ny && ny < n)) continue;
if (e[nx][ny] != 'X') continue;
if (col[nx][ny] == -1) dfs(nx, ny, 1 - c);
ans = max(ans, 2);
if (col[nx][ny] == c) ans = max(ans, 3);
}
}
int main() {
int i, j;
scanf("%d", &n);
for (i = 0; i < n; ++i) scanf("%s", e[i]);
memset(col, -1, sizeof(col));
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (e[i][j] == 'X' && col[i][j] == -1)
dfs(i, j, 0);
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이