#1018 : 체스판 다시 칠하기

풀이방법

사용된 것:

브루트포스 알고리즘

 

2022.04.21

가능한 수를 모두 구하고 그 중 최솟값을 출력하면 된다.

처음엔 브루트포스로 풀면 시간초과가 날까봐 다른 방법을 생각해내려 애썼다.

그런데 전혀 생각이 나지 않았다... 그래서 문제의 카테고리를 펼쳐보니, 이럴 수가 브루트포스 문제였다.

그냥 다 구하면 된다. 알고리즘은 다음과 같다.

 

칸의 색이 흰색 혹은 검은색으로 두 가지이므로 boolean값을 이용해 색을 구분하였다.

검은색은 true로, 흰색은 false로 하였다.

 

하나의 8$\times$8 크기 구획 내에서 고쳐야 하는 칸의 최소 개수를 구하는 함수를 정의한다.

그리고, 이 함수를

해당 체스판에서 만들어질 수 있는 모든 8$\times$8 크기 구획에 대하여 수행하면 된다.

그 중 최솟값을 화면에 출력하면 해결이다.

 

이 함수의 형식은 다음과 같다.

해당 8$\times$8 크기 구역의 가장 왼쪽 위 칸이

검은색이어야 하는 경우에 고쳐야 하는 칸의 개수,

흰색이어야 하는 경우에 고쳐야 하는 칸의 개수

이렇게 두 가지를 구하여 둘 중 작은 수를 리턴한다.

 

체스판의 크기는 행이 N개, 열이 M개이다.

체스판에서 나올 수 있는 8$\times$8 크기의 구획의 개수는 (N-7)$\times$(M-7)개이다.

총 (N-7)$\times$(M-7)번만큼 위의 함수를 수행한다. 그 결과값들 중 최솟값이 정답이다.

 

코드

Java(2022.04.21)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static boolean[][] plate;
	
	static int getNum(int row, int col) {
		//row와 col은 이번 구역의 가장 왼쪽 위 칸의 좌표
		int num1 = 0;
		int num2 = 0;
		
		//첫 칸이 검은색이어야 옳다고 가정할 때
		boolean b = true;
		//b가 true인 채로 시작
		for(int i = row; i<row+8; i++) {
			for(int j = col; j<col+8; j++) {
				if(plate[i][j]!=b) num1++;
				if(b) b = false;
				else b = true;
			}
			if(b) b = false;
			else b = true;
		}
		
		//첫 칸이 흰색이어야 옳다고 가정할 때
		b = false;
		//b가 false인 채로 시작
		for(int i = row; i<row+8; i++) {
			for(int j = col; j<col+8; j++) {
				if(plate[i][j]!=b) num2++;
				if(b) b = false;
				else b = true;
			}
			if(b) b = false;
			else b = true;
		}
		
		//둘 중 작은 쪽을 리턴
		return Math.min(num1, num2);
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//행 수(N), 열 수(M)
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		//체스판 읽어오기
		plate = new boolean[n][m];
		//검은색은 true, 흰색은 false
		for(int i = 0; i<n; i++) {
			char[] input = br.readLine().toCharArray();
			for(int j = 0; j<m; j++) {
				if(input[j] == 'W') plate[i][j] = false;
				else plate[i][j] = true;
			}
		}
		
		//정답 구하기
		int r = n - 7;
		int c = m - 7;
		int answer = n*m;	//나올 수 있는 최댓값을 저장해두기
		//getNum으로 나오는 모든 값 중 최솟값을 정답으로 취하기
		for(int i = 0; i<r; i++) {
			for(int j = 0; j<c; j++) answer = Math.min(answer, getNum(i, j));
		}
		
		//정답 출력
		System.out.print(answer);

	}

}