[백준] 1018번 : 채스판 다시 칠하기

1018번: 체스판 다시 칠하기

해당 문제는 완전탐색문제로 8x8 채스판을 뒤집을 수 있는 최소 개수를 구하는 문제입니다.

깊이 우선탐색으로 문제를 해결하였으며 전체 채스판에서 모든 8x8 채스판을 확인합니다.

0x0이 ‘W’일때와 0x0이 ‘H’ 일때 2가지 경우를 모두 탐색합니다.

# <https://www.acmicpc.net/problem/1018>
move = ((0,1), (1,0), (0, -1), (-1, 0))

N, M = map(int, input().split())
graph = []
CHAR = ["W", "B"]
WHITE = 0
BLACK = 1

def dfs(i, j, cur, visited):
    global cnt, h, w, h2, w2
    if graph[i][j] != cur:
        cnt += 1
    
    for dy, dx in move:
        ny, nx = i +dy, j+dx
        if h >= ny >= h2 and w >= nx >= w2 and not visited[ny][nx]:
            visited[ny][nx] = True
            if cur == CHAR[WHITE]:
                dfs(ny, nx, CHAR[BLACK], visited)
            else:
                dfs(ny, nx, CHAR[WHITE], visited)
            
    

minresult = N*M
for _ in range(N):
    graph.append(list(map(str, input())))
    
for i in range(N):
    for j in range(M):
        h, w, cnt = i+7, j+7, 0
        h2 , w2 = i, j
        #print(N,M ,h,w, cnt)
        if N > h >=0 and M > w >=0:
            visited = [[False for _ in range(M)] for _ in range(N)]
            #print(i,j, "시작")

            visited[i][j] = True
            dfs(i,j,'W', visited)
            #print(visited)
            #print("White",cnt)
            minresult = min(cnt, minresult)

            visited = [[False for _ in range(M)] for _ in range(N)]

            cnt = 0
            visited[i][j] = True
            dfs(i,j, 'B', visited)
            #print("Black",cnt)
            minresult = min(cnt, minresult)
        
print(minresult)