BOJ 1018 - 체스판 다시 칠하기

문제

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

1018번: 체스판 다시 칠하기

 

 

풀이

8*8 크기의 체스판을 두 개를 준비한다. W로 시작하는 체스판과 B로 시작하는 체스판을 준비한다.

이 두 체스판을 M*N 크기의 보드에 번갈아 가면서 비교해 가면 된다.

 

1. M*N 보드의 왼쪽 끝(0,0)을 기준으로 8*8 크기 만큼 두 개의 체스판과 비교를 한다.

2. 왼쪽 끝을 (0,1), (0,2), ..., (1,0), (1,1), ... 순으로 가능한 범위 내에서 바꿔준 후 8*8 크기 만큼 두 개의 체스판과 비교를 한다.  

3. 비교할 때 마다 비교 횟수를 구한 후 최소값과 비교한다.

 

 

코드

C++

#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
string board[50];
int N, M;
int result = 987654321;
 
string c1[8] = { "WBWBWBWB", 
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW"};
                
string c2[8] = { "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB"};
 
int check1(int x, int y)
{
    int diff = 0;
    for (int i=x; i<x+8; i++)
        for (int j=y; j<y+8; j++)
            if (board[i][j] != c1[i-x][j-y])
                diff++;
    return diff;
}
 
int check2(int x, int y)
{
    int diff = 0;
    for (int i=x; i<x+8; i++)
        for (int j=y; j<y+8; j++)
            if (board[i][j] != c2[i-x][j-y])
                diff++;
    return diff;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
 
    for (int i=0; i<N; i++)
        cin >> board[i];
 
    for (int i=0; i<=N-8; i++)
        for (int j=0; j<=M-8; j++)
            result = min(result, min(check1(i, j), check2(i,j)));  
       
    cout << result;
 
    return 0;
}

 

python

board = []
answer = 50 * 50 + 1
 
n, m = map(int, input().split())
 
for _ in range(n):
    board.append(input())
 
for r in range(n - 7):
    for c in range(m - 7):
        case_1 = 0  # WB
        case_2 = 0  # BW
 
        for i in range(r, r + 8):
            for j in range(c, c + 8):
                if (i + j) % 2 == 0:
                    if board[i][j] == "B":  # WB
                        case_1 += 1
                    if board[i][j] == "W":  # BW
                        case_2 += 1
                else:
                    if board[i][j] == "W":  # WB
                        case_1 += 1
                    if board[i][j] == "B":  # BW
                        case_2 += 1
 
        answer = min(answer, case_1, case_2)
 
 
print(answer)
 

 

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    private static int n, m;
    private static char[][] arr;
 
    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
 
    private static void solve() {
        int result = n * m;
        for (int i = 0; i < n - 7; i++) {
            for (int j = 0; j < m - 7; j++) {
                result = Math.min(result, Math.min(check(i, j, 'B'), check(i, j, 'W')));
            }
        }
        System.out.println(result);
    }
 
    private static int check(int i, int j, char bw) {
        int cnt = 0;
        for (int y = 0; y < 8; y++) {
            for (int x = 0; x < 8; x++) {
                if ((y + x) % 2 == 1) {
                    if (arr[i + y][j + x] == bw) {
                        cnt++;
                    }
                } else {
                    if (arr[i + y][j + x] != bw) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
 
    private static void input() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(split[0]);
        m = Integer.parseInt(split[1]);
        arr = new char[n][m];
        for (int i = 0; i < n; i++) {
            split = bufferedReader.readLine().split("");
            for (int j = 0; j < m; j++) {
                arr[i][j] = split[j].charAt(0);
            }
        }
    }
 
}