[JAVA] 백준 1018번 체스판 다시 칠하기 : 정반대 경우의 수

1018번: 체스판 다시 칠하기

 

1. 문제 추상화

 

M X N 크기의 보드를 8X8로 잘라 체스판을 만들려 한다. M X N의 보드는 격자마다 무작위로 색칠되어 있을 때, 어느 부분을 8X8로 잘라야 최소한의 색칠로 8X8체스판을 만들 수 있을까? ( 체스판은 격자간 색깔이 겹치면 안 된다. )

 

2. 알고리즘 

 

알고리즘 구상은 쉬우나 사소한 조건을 놓칠 수 있어 코드 구현이 만만치 않은 문제이다. 나는 두 가지 방법으로 풀었다. 첫 번째 방법은 나의 알고리즘이고 두 번째 방법은 인터넷에서 찾아본 방법이다.

 

※ MxN 보드에서 가능한 모든 8 x 8 영역을 조사하여 최솟값을 구하는 문제 ( 브루트 포스 )

 

▷ 첫 번째 방법 ( 나의 알고리즘 )

1 .8x8 체스판 모범답안을 만든 후 MxN 보드에서 선택된 8x8 영역과 비교하여 틀린 부분 카운트 하기

( 모범답안 : 격자무늬 체크판 )

 

▷ 두 번째 방법 ( 인터넷 풀이 )

1. M X N 보드를 boolean 이차원 배열로 구성

2. 체스판은 격자무늬이므로 선택된 8x8 영역에서 TRUE나 FALSE가 연속되면 카운트 하기

 

나는 문제를 풀면서 두 알고리즘을 모두 생각했었다. 그러나 풀이에 난항을 겪었다. 그 이유는 모범답안이 두 개라는 사실을 인지하지 못했기 때문이다. 체스판은 항상 맨 왼쪽 위의 색이 디폴트로 정해져 있지않다. 검은색이나 흰색 둘 중 하나이다.

 

그러므로 두 가지 경우의 수를 모두 고려해야한다. 간단히 3 x 3 체스판을 생각해보자. 

 

▶ 모범답안 1

 

 

 

 

 

 

 

 

 

▶ 모범답안 2

 

모범 답안 두 개는 패턴이 정반대이다.

그러므로 한 모범답안에서 틀린 격자는 다른 모범답안에서는 정답이다. 

 

예시

MxN 보드에서 해당 3x3 영역을 선택했다고 해보자. 모범답안1에서는 정가운데 격자만 틀리고 나머지는 정답이다. 그렇다면 모범답안2에는 어떨까? 정반대이다. 정가운데만 맞고 나머지는 모두 틀렸다. 패턴이 정반대이기에 맞고 틀린 격자도 정반대이다. 그러므로 9개의 격자 중 모범답안1이 3개를 고쳐야 한다면 모범답안2는 6개를 고쳐야한다.

 

그러므로 8x8의 체크판은 64개의 격자가 있으므로 모범답안1이 4개를 고쳐야 한다면 모범답안2는 60개를 고쳐야한다.

 

고로 알고리즘을 사용하여 한 가지 모범답안에서의 체크판 수정횟수(count)를 구한 다음 다른 모범답안에서의 수정횟수는 64에서 A를 빼주어서 구한다. 그 후, 두 수정횟수 중 최솟값을 구하면 된다.

 

3. 코드

 

첫 번째 방법

 

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

public class Main {
	
	private static final int PIVOT = 8;

	private static BufferedReader br;
	private static BufferedWriter bw;
	private static StringTokenizer stz;
	
	private static int height;
	private static int width;
	
	private static char[][] chess;

	public static void main(String[] args) throws IOException {
		createIOObjects();
		getChess();
		printResult(getMinChange());
	}
	
	public static void createIOObjects() {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
	}
	
	public static void getChess() throws IOException {
		createChess();
		initializeChess();
	}
	
	public static void printResult(int result) throws IOException {
		bw.write(result+"");
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static int getMinChange() {
		int min = width*height;
		for(int i=0; i+PIVOT<=height;i++) {
			for(int j=0; j+PIVOT<=width;j++) {
				int tmp = countChange(i,j);
				if(tmp < min) min = tmp;
			}	
		}
		return min;
	}

	public static void createChess() throws IOException {
		stz = new StringTokenizer(br.readLine());
		height = Integer.parseInt(stz.nextToken());
		width  = Integer.parseInt(stz.nextToken());
		
		chess = new char[height][width];
	}
	
	public static void initializeChess() throws IOException {
		for(int i=0;i<height;i++) {
			String value = br.readLine();
			for(int j=0; j<width;j++) {
				chess[i][j] = value.charAt(j);
			}
		}
	}
	
	public static int countChange(int startHeight, int startWidth) {
		 char[][] pivotChess = makePivotChess('W'); // 모범답안1
         
		 int whiteMin = getCount(pivotChess,startHeight,startWidth); // 모범답안1 수정횟수
		 int blackMin = 64 - whiteMin; // 64 - 모범답안1 수정횟수
		 return Math.min(whiteMin, blackMin); // 최솟값 리턴
	}
	
    // 모범답안 생성
	public static char[][] makePivotChess(char start) {
		
		char[][] pivotChess = new char[PIVOT][PIVOT];
		char even = 'W';
		char odd  = 'B';
	
		for(int i=0;i<PIVOT;i++) {
			for(int j=0;j<PIVOT;j++) {
				if(j%2==0) {
					pivotChess[i][j] = even;
				}else {
					pivotChess[i][j] = odd;
				}
			}
			char tmp = even;
			even = odd;
			odd = tmp;
		}
		
		return pivotChess;
	}
	// 모범답안과 비교하여 수정횟수 구하기
	public static int getCount(char[][] pivotChess, int startHeight,int startWidth) {
		int count = 0;
		for(int i=0;i<PIVOT;i++) {
			for(int j=0;j<PIVOT;j++) {
				if(chess[i+startHeight][j+startWidth] != pivotChess[i][j]) count++;
			}
		}
		return count;
	}
}

 

 

두 번째 방법 

 

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

public class Main {
	
	private static final int PIVOT = 8;

	private static BufferedReader br;
	private static BufferedWriter bw;
	private static StringTokenizer stz;
	
	private static int height;
	private static int width;
	
	private static boolean[][] chess;


	public static void main(String[] args) throws IOException {
		createIOObjects();
		getChess();
		printResult(getMinChange());
	}
	
	public static void createIOObjects() {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
	}
	
	public static void getChess() throws IOException {
		createChess();
		initializeChess();
	}
	
	public static void printResult(int result) throws IOException {
		bw.write(result+"");
		bw.flush();
		bw.close();
		br.close();
	}
	
	public static int getMinChange() {
		int min = width*height;
		for(int i=0; i+PIVOT<=height;i++) {
			for(int j=0; j+PIVOT<=width;j++) {
				int tmp = getCount(i,j);
				if(tmp < min) min = tmp;
			}	
		}
		return min;
	}
	
	public static void createChess() throws IOException {
		stz = new StringTokenizer(br.readLine());
		height = Integer.parseInt(stz.nextToken());
		width  = Integer.parseInt(stz.nextToken());
		
		chess = new boolean[height][width];
	}
	
	public static void initializeChess() throws IOException {
		for(int i=0;i<height;i++) {
			String value = br.readLine();
			for(int j=0; j<width;j++) {
				if(value.charAt(j)=='W') { //'W'는 false
					chess[i][j] = false;
				}
				else if(value.charAt(j)=='B') {
					chess[i][j] = true;
				}
			}
		}
	}
	
	public static int getCount(int startHeight,int startWidth) {

		boolean current = chess[startHeight][startWidth];
		int count = 0;
		
		for(int i=0;i<PIVOT;i++) {
			for(int j=0;j<PIVOT;j++) {
				if(current != chess[i+startHeight][j+startWidth]) count++;
				current = !current;
			}
			current = !current;
		}
		return Math.min(count, PIVOT*PIVOT-count);
	}
}