[Python/Java] 백준 1018 - 체스판 다시 칠하기 [Brute Force]

문제

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

 

해설

BFS로 접근하는 것으로 착각하여 시간 소비를 많이 하였다. Brute Force를 이용하여 완전 탐색을 진행하면 쉽게 해결할 수 있는 문제였다.

 

Python

from sys import stdin


def brute_force(matrix: list, x: int, y: int):
    w_start = 0
    b_start = 0

    for i in range(8):
        for j in range(8):
            if (i+j) % 2 == 0:
                if matrix[x+i][y+j] != "W":
                    w_start += 1
                elif matrix[x+i][y+j] != "B":
                    b_start += 1
            else:
                if matrix[x+i][y+j] != "B":
                    w_start += 1
                elif matrix[x+i][y+j] != "W":
                    b_start += 1

    return min(w_start, b_start)


n, m = map(int, stdin.readline().split(" "))
board = [list(stdin.readline().strip()) for _ in range(n)]

result = []
for row in range(n-7):
    for col in range(m-7):
        result.append(brute_force(board, row, col))
print(min(result))

 

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] condition = br.readLine().split(" ");
        int n = Integer.parseInt(condition[0]);
        int m = Integer.parseInt(condition[1]);
        
        List<List<String>> matrix = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            matrix.add(new ArrayList<>(Arrays.asList(br.readLine().trim().split(""))));
        }
        
        List<Integer> result = new ArrayList<>();
        for(int row=0; row<n-7; row++){
            for(int col=0; col<m-7; col++){
                result.add(bruteForce(matrix, row, col));
            }
        }

        System.out.println(Collections.min(result));
    }

    static int bruteForce(List<List<String>> matrix, int x, int y) {
        int wStart = 0;
        int bStart = 0;

        for(int i=0; i<8; i++){
            for(int j=0; j<8; j++) {
                if((i + j) % 2 == 0) {
                    if(!matrix.get(x + i).get(y + j).equals("W")) { wStart++; }
                    if(!matrix.get(x + i).get(y + j).equals("B")) { bStart++; }
                } else {
                    if(!matrix.get(x + i).get(y + j).equals("B")) { wStart++; }
                    if(!matrix.get(x + i).get(y + j).equals("W")) { bStart++; }
                }
            }
        }

        return Math.min(bStart, wStart);
    }
}