[Java] 백준 1018번 문제 '체스판 다시 칠하기' 풀이

이번 문제도 브루트 포스 문제입니다

일단 문제 먼저 보시겠습니다

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

1018번: 체스판 다시 칠하기

문제를 보면 그냥 탐색해서 비교만 하면 될 것 같지만

MxN의 넓은 보드에서 8x8만큼의 체스판 크기로 뽑은 다음

하나하나 비교를 해봐야합니다

 

그래서 저는 for문을 4개나 쓰는 방법을 생각했습니다

(다른 방법이 있으신 분들은 댓글로 알려주시면 감사하겠습니다!!!)

 

그리고 문제에서 힌트를 하나 발견했습니다

바로 '체스판을 칠하는 경우는 두 가지뿐이다.'라는 말입니다

그러니 완성된 체스판의 예시를 두 개만 가지고 하나하나씩 비교를 하면 됩니다

특별한 비교 방법을 사용하는 것이 아닌 단순한 비교만 하는 것이라

생각보다 간단합니다

 

그러나 코딩하기에는 조금 이쁘지는 않았습니다

일단 코드부터 보시겠습니다

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

public class Main {
	//체스판이 만들어지는 모양의 경우의 수는 두 가지뿐이니 예시로 chess1과 chess2를 만든다
	static final char[][] chess1 = {
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'}
	};
	
	static final char[][] chess2 = {
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'},
			{'B','W','B','W','B','W','B','W'},
			{'W','B','W','B','W','B','W','B'}
	};
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		// 값을 입력 받기 위한 BufferedReader
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		int row = Integer.parseInt(str.nextToken());
		int colunm = Integer.parseInt(str.nextToken());
		
		
		String[] board = new String[row]; //원본 판을 저장하기위한 String배열
		int min = Integer.MAX_VALUE;      //바뀌는 수의 최소값을 저장하기 위한 배열
		
		for(int i = 0 ; i < row ; i++){
			board[i] = br.readLine();
		}
		
		for(int i = 0 ; i <= row - 8; i++) {
			for(int j = 0 ; j <= colunm - 8; j++) {
				int change1 = 0; //chess1과 비교했을 때 바꿔야하는 횟수
				int change2 = 0; //chess2와 비교했을 때 바꿔야하는 횟수
				for(int k = j ;k < j + 8; k++) {
					for(int l = i;l < i + 8; l++) {
						if(board[l].charAt(k) != chess1[l-i][k-j]) change1++;
						if(board[l].charAt(k) != chess2[l-i][k-j]) change2++;	
					}
				}
				if(change1 < min || change2 < min) {
					min = Math.min(change1, change2);
				}
			}
		}
		System.out.println(min);	
	}

}

첫 번째, 두 번째 for문 먼저 설명드리자면

일단 모든 board에서 뽑을 수 있는 체스판 후보들을 선택해야 합니다

그래서 board의 끝에서 8씩 빼준 값까지만 시작점으로 생각하고 탐색을 시작합니다

(만약 13x20의 board를 가지고 탐색한다면 행은 5번째까지, 열은 12번째까지가 체스판의 시작점으로 올 수 있습니다)

 

board의 일부를 떼어낸 8x8 크기의 체스판 후보가 선택되었습니다

그리고 세 번째, 네 번째 for문에서는 chess1과 chess2를 선택된 체스판 후보와 비교합니다

chess1과 비교해서 색을 다시 칠해야할 칸은 change1에 카운트되고,

chess2과 비교해서 색을 다시 칠해야할 칸은 change2에 카운트됩니다.

 

그래서 이 두 change가 min보다 작은지 확인한 다음

두 change 중 작은 값을 선택해서 min에 저장하고 출력하면 답이 나옵니다

 

 

이 문제는 체스판이 나오는 경우의 수가 두 가지라는 점과 넓은 board의 일부만 봐야하는 것만 잘 처리해주면

간단하게 풀리는 문제인 것 같습니다

저는 그것보다 Scanner를 안 쓰고 BufferedReader가 아직 익숙하지 않아서 공부하면서 풀다보니

시간이 오래걸렸네요...ㅎㅎㅎ

그리고 이런 문제는 별로 풀고 싶지 않네요

뭔가 노가다하는 느낌이랄까..??

 

그럼 읽어주셔서 감사합니다!!!