[Baekjoon] 육각 보드

문제

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

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

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

입력

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

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

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

출력

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

예제

Example 1:

Input: 
3
---
---
---
Output: 
0

Example 2:

Input:
4
-X--
---X
----
-X--
Output:
1

Example 3:

Input:
4
XXXX
---X
---X
---X
Output:
2

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이 1

나올 수 있는 값은 최대 3이다. dfs를 들어가지 않는 다면, 0이고 들어간다면 1은 보장된다. 그 후, 이분 그래프문제와 같은 방식으로 이분 그래프가 된다면 2이고 안된다면 3이다.

import sys
sys.setrecursionlimit(10**9)

n = int(input())

board = []

for _ in range(n):
    board.append(list(input()))

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

ans = 0

def dfs(x, y):
    global ans
    ans = max(ans, 1)

    # 다음 방향
    for k in range(6):
        nx, ny = x+ dx[k], y+ dy[k]

        if 0 <= nx < n and 0 <= ny <n and board[nx][ny] == 'X':
            if  visited[nx][ny] == 0:
                visited[nx][ny] = -visited[x][y]
                dfs(nx, ny)
                ans = max(ans, 2)
            else:
                if visited[nx][ny] == visited[x][y]:
                    ans = max(ans, 3)
                    return

visited = [[0]*n for _ in range(n)]

for x in range(n):
    for y in range(n):
        if board[x][y] == 'X' and visited[x][y] == 0:
            visited[x][y] = 1
            dfs(x, y)


print(ans)