[코테] 백준 그래프 12946번 문제

12946번 : 육각 보드

문제 링크

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

문제 설명

크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다.

육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.

어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄부터 N개의 줄에는 어떤 칸을 색칠해야 하는지에 대한 정보가 주어진다.

i번째 줄의 j번째 문자는 (i, j)칸의 정보를 나타내고, ‘-‘인 경우는 색칠하지 않는 것이고 ‘X’면 색칠해야 하는 것이다.

출력

첫째 줄에 필요한 색의 종류의 최솟값을 출력한다.

문제풀이

처음에는 인접한 색칠하는 칸이 제일 많은 칸수를 출력하게 구성하였으나 틀렸다. 이유는 육각 보드의 경우 총 3가지 색으로도 모든 칸을 칠할 수 있다는 함정이 있었다. 따라서 dfs로 주변 인접한 칸을 색칠해가면서 주변에 2개 칸이 색칠해야 하는 칸이면 3가지 색으로 색칠해야 하는 것이다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

dy = [-1, -1, 0, 0, 1, 1]
dx = [0, 1, -1, 1, -1, 0]

def dfs(y, x, cnt) :
    global result
    result = max(result, 1)
    visited[y][x] = cnt
    
    for i in range(6) : 
        ny, nx = y+dy[i], x+dx[i]
        if not (0 <= ny < N) or not (0 <= nx < N) : 
            continue
        if graph[ny][nx] == 'X' and visited[ny][nx] == -1 :
            dfs(ny, nx, 1-cnt)
            result = max(result, 2)
        if visited[ny][nx] == cnt : 
            result = max(result, 3)

N = int(input())
graph = [list(input()) for _ in range(N)]
visited = [[-1 for _ in range(N)] for _ in range(N)]
result = 0

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(result)