[JAVA] 백준 1018 체스판 다시 칠하기_부르트포스

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

1018번: 체스판 다시 칠하기

 

접근 :

 

- 체스판이 칠해질 수 있는 경우의 수는 검은색(B)으로 시작하는 경우와 흰색(W)으로 시작하는 경우로 나눌 수 있다.

 

 

- 또한 8X8의 크기를 가질 수 있고, N / M 이 각각 8 이상의 크기를 가질 수 있다.

 

 

- 그러므로 8 X 8 의 크기로 나누어 이동하면서 각각의 경우의 최소의 다시 칠하는 경우의 수를 계산한다.

- 0.0 을 기준으로 x, y를 각각 1씩 offset을 주면서 모든 경우의 수를 구한다.

- 8 X 8 크기의 판에서는 B로 시작하는경우 W로 시작하는 경우 각각을 계산하여 최소의 값을 구한다.

 

 

코드 구현

 

import java.io.*;

public class Main {

	// 8*8 배열판에 잘못 칠해진 칸의 갯수가 몇개인지 찾는 메서드
	public static int searchboard(char[][] board, int x_offset, int y_offset) {
		// B 로 시작하는 경우 true;
		boolean start_b = false;
		// W 로 시작하는 경우 몇개의 칸을 다시 칠해야 하는지 결과값
		int result_w = 0;
		// B 로 시작하는 경우 몇개의 칸을 다시 칠해야 하는지 결과값
		int result_b = 0;

		for (int i = y_offset; i < 8 + y_offset; i++) {
			for (int j = x_offset; j < 8 + x_offset; j++) {
				// 잘못 칠해진 경우 카운트 증가
				if (start_b) {
					result_w = (board[i][j] == 'W') ? result_w : result_w + 1;
					result_b = (board[i][j] == 'B') ? result_b : result_b + 1;
				} else {
					result_w = (board[i][j] == 'B') ? result_w : result_w + 1;
					result_b = (board[i][j] == 'W') ? result_b : result_b + 1;
				}
				// 옆 칸으로 옮겨 갈때 반전 B인 경우 W, W인 경우 B
				start_b = !start_b;
			}
			// 아랫 줄로 옮겨 갈 때 반전 B인 경우 W, W인 경우 B
			start_b = !start_b;
		}
		// 최소의 경우를 결과값으로 리턴
		return (result_w < result_b) ? result_w : result_b;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs = br.readLine().split(" ");
		int n = Integer.parseInt(inputs[0]);
		int m = Integer.parseInt(inputs[1]);
		String rawdata;

		// 결과값 최대값을 저장
		int result = Integer.MAX_VALUE;
		// 임시 결과값 0 으로 셋팅 (n,m이 8보다 작은경우 예외처리)
		int temp_result = 0;
		char[][] board = new char[n][m];

		// 입력된 값을 n*m char 2차 배열로 저장
		for (int col = 0; col < n; col++) {
			rawdata = br.readLine();
			for (int row = 0; row < m; row++) {
				board[col][row] = rawdata.charAt(row);
			}
		}

		// 8 X 8 의 모양으로 기준점 0.0 을 기준으로 shift 하면서 최소값을 찾음
		for (int y_offset = 0; y_offset + 8 <= n; y_offset++) {
			for (int x_offset = 0; x_offset + 8 <= m; x_offset++) {
				// B로 시작하는 경우 W로 시작하는 경우중 최소의 결과값 temp_result에 저장
				temp_result = searchboard(board, x_offset, y_offset);
				// 최소의 값을 결과값에 저장
				result = temp_result < result ? temp_result : result;
			}
		}
		System.out.println(result);
	}
}