체스판 다시 칠하기 풀이

문제 링크: https://www.acmicpc.net/problem/1018

백준 브루트 포스 4단계 - 1018번 체스판 다시 칠하기를 풀어보았다.

 

풀이: 첫 칸이 흰색인 경우와 검은색인 경우로 나뉘기 때문에 그 점을 신경 써야 한다.

C++의 경우, 체스보드를 만들어놓고 풀었다.

 

C++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 987654321;
const int MAX = 50;

int M, N;
string board[MAX];
//(0, 0)이 W인 체스보드
string whiteFirst[8]={{"WBWBWBWB"},{"BWBWBWBW"},{"WBWBWBWB"},{"BWBWBWBW"},{"WBWBWBWB"},
                      {"BWBWBWBW"},{"WBWBWBWB"},{"BWBWBWBW"}};

//(0, 0)이 B인 체스보드
string blackFirst[8]={{"BWBWBWBW"},{"WBWBWBWB"},{"BWBWBWBW"},{"WBWBWBWB"},{"BWBWBWBW"},
                      {"WBWBWBWB"},{"BWBWBWBW"},{"WBWBWBWB"}};

//(0, 0)이 W인 체스보드 기준 바뀔 칸 수
int whiteFirstChange(int y, int x)
{
    int cnt = 0;
    for (int i = y; i < y + 8; i++)
    {
        for (int j = x; j < x + 8; j++) if (board[i][j] != whiteFirst[i - y][j - x]) cnt++;
    }
    return cnt;
}
//(0, 0)이 B인 체스보드 기준 바뀔 칸 수
int blackFirstChange(int y, int x)
{
    int cnt = 0;
    for (int i = y; i < y + 8; i++)
    {
        for (int j = x; j < x + 8; j++) if (board[i][j] != blackFirst[i - y][j - x]) cnt++;   
    }
    return cnt;
}

int main(void)
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> board[i];
    int result = INF;
    for (int i = 0; i + 7 < N; i++)
    {
        for (int j = 0; j + 7 < M; j++)
        {
            result = min(result,min(whiteFirstChange(i,j),blackFirstChange(i,j)));
        }
    }
    cout << result << endl;
    return 0;
}

Python

n,m=map(int,input().split())
board=[] # 체스판
check=[] # 다시 칠해야하는 칸 수
for i in range(n):
	board.append(input())
for a in range(n-7): # 8X8 사이즈로 자르기 위해 7을 빼줌
	for b in range(m-7):
		white=0 # 첫칸이 흰색일때
		black=0 # 첫칸이 검은색때
		for i in range(a,a+8):
			for j in range(b,b+8):
				if (i+j)%2==0: # 지금 칸이 시작점과 색이 같아야 하면
					if board[i][j]!='W': # 첫칸 흰색인데 흰색이 아니면
						white+=1
					if board[i][j]!='B': # 첫칸 검은색인데 검은색이 아니면
						black+=1
				else: # 지금 칸이 시작점과 색이 달라야 하면
					if board[i][j]!='B': 
						white+=1
					if board[i][j]!='W':
						black+=1
		check.append(min(white,black)) # 두 값중 작은걸로
print(min(check))

Java