코드 복사/붙여넣기 하는 당신이 아름답습니다.

12946 : 육각보드

풀이

잘 생각해보면 보드는 최대 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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-03-06 15:18

Read more posts by this author