[백준]12946 :육각보드

DFS

문제: 육각보드

육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.
어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오.

잠깐 상식!
'4색 정리', 4가지 색으로 어떤 지도든 서로 다른 색으로 칠할 수 있다?

전세계 지도를 4가지 색깔만으로 전부 색칠할 수 있는거 알고있었나요? 참 신기합니다요
이 문제도 아무리 많은 육각형이 있어도 최대 3개의 색깔만 있으면 색칠 할 수 있다는 것을 알면 풀 수있는문제였습니다.

육각형이기 때문에 세 면이 맞닿는 노드가 있을 수 있습니다. 이러한 노드가 있는지 확인하는 것이 중요합니다.
(0, 1), (0, 2), (1, 1)
1012
0101
1010
0101

이게 무슨말이냐면요, 나의 색깔은 1이고 내 옆 노드의 색깔은 0이라고 하면 그 옆노드는 1로 번갈아 가면서 채우면 되는데 내 인접한노드 (예를 들어 육각형의 오른쪽 대각선 노드)가 이미 1이라면 인접해서 놓을 수 없으니 하나의 색깔을 더 추가해야 한다는 것입니다.
그래서 최대 3개까지 결과 값을 가질 수 있고 순회가 끝나면 가장 큰 값을 출력하면 됩니다.

앞으로 색을 채우는 문제는 0과 1의 반복으로 풀어가면 되겠어요

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n = int(input())
graph = []
for i in range(n):
	graph.append(list(input()))
dx = [-1, -1, 0, 0, 1, 1]
dy = [0, 1, -1, 1, -1, 0]
ans = 0
def dfs(x, y, cnt):
	global ans
	visited[x][y] = cnt
	ans = max(ans, 1)
	for i in range(6):
		nx = x + dx[i]
		ny = y + dy[i]
		if nx < 0 or ny < 0 or nx >= n or ny >= n:
			continue
        #번갈아 가면서 두기 0, 1, 0, 1
		if graph[nx][ny] == 'X' and visited[nx][ny] == -1:
			dfs(nx, ny, 1-cnt)
			ans = max(ans, 2)
        # 인접한 노드의 값이 나와 같으면 하나 더 필요 
		if visited[nx][ny] == cnt:
			ans = max(ans, 3)


visited = [[-1]* n for _ in range(n)]
for i in range(n):
	for j in range(n):
		if graph[i][j] == 'X' and visited[i][j] == -1:
			dfs(i, j, 0)
print(ans)