취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 12946번 문제인 육각 보드이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/12946

예제 입력 1과 같이 칠할 칸이 없다면 답은 0이 된다. 다음 문단부터는 칠할 칸이 존재한다고 가정하겠다.

세 가지 색의 이름을 각각 A, B, C라 할 때, 행마다 색을 "ABCABCABCA...", "CABCABCABC...", "BCABCABCAB..."와 같이 돌아가면서 칠하면 모든 칸을 인접한 칸의 색이 다르게 칠할 수 있음을 관찰하자. 따라서 문제의 답은 항상 3 이하이다.

한편, 어떤 칸을 두 가지 이하의 색으로 칠할 수 있다는 것은 칸을 노드로 갖고 인접관계를 에지로 갖는 그래프가 이분 그래프(bipartite graph)와 같다는 것과 동치임을 관찰하자. 이를 이용해 칠해야 하는 칸들이 이분그래프의 형태로 나타나는지 여부를 이용해 답이 3인지 아닌지를 판정할 수 있다.

또한 한 가지 색만으로 주어진 그래프를 칠할 수 있으려면 서로 인접한 칸이 없어야 함을 관찰하자. 이를 이용해 이분그래프를 두 가지 색으로 칠해야하는지 한 가지 색으로 칠해야하는지를 구분지을 수 있다.

위의 내용을 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
string board[50];
int dist[50][50];
int dr[6] = {0,-1,-1,0,1,1};
int dc[6] = {-1,0,1,1,0,-1};
bool chk1, chk2, chk3;
void dfs(int r, int c) {
	for (int i = 0; i < 6; i++) {
		int rr = r + dr[i], cc = c + dc[i];
		if (rr < 0 || rr >= N || cc < 0 || cc >= N || board[rr][cc] == '-') continue;
		if (dist[rr][cc]) {
			if ((dist[r][c] + dist[rr][cc]) % 2 == 0) chk3 = 1;
		}
		else {
			dist[rr][cc] = dist[r][c] + 1;
			dfs(rr, cc);
		}
		chk2 = 1;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < N; r++) cin >> board[r];

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c] == '-' || dist[r][c]) continue;
			chk1 = 1;
			dist[r][c] = 1;
			dfs(r, c);
		}
	}
	if (chk3) cout << 3;
	else if (chk2) cout << 2;
	else if (chk1) cout << 1;
	else cout << 0;
}