1018번: 체스판 다시 칠하기

문제 풀러가기

1018

설명

BP 알고리즘이다. 모든 칸을 시작지점으로 생각하고 경우의 수를 찾아서 최소한의 값을 찾아 출력하도록 만든다.

코드

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

class Main {
	public static boolean[][] arr;
	public static int min = 64;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		arr = new boolean[N][M];

		// 배열 입력
		for(int i = 0; i < N; i++) {
			String str = br.readLine();

			for(int j = 0; j < M; j++) {
				if(str.charAt(j) == 'W') {
					arr[i][j] = true;		// W일 때는 true
				} else {
					arr[i][j] = false;		// B일 때는 false
				}
			}
		}

		int N_row = N - 7;
		int M_col = M - 7;

		for(int i = 0; i < N_row; i++) {
			for(int j = 0; j < M_col; j++) {
				find(i, j);
			}
		}
		System.out.println(min);
	}

	public static void find(int x, int y) {
		int end_x = x + 8;
		int end_y = y + 8;
		int count = 0;

		boolean TF = arr[x][y];	// 첫 번째 칸의 색

		for(int i = x; i < end_x; i++) {
			for(int j = y; j < end_y; j++) {

				// 올바른 색이 아닐경우 count 1 증가
				if(arr[i][j] != TF) {
					count++;
				}

				/*
				 * 다음 칸은 색이 바뀌므로
				 * true라면 false로, false 라면 true 로
				 * 값을 변경한다.
				 */
				TF = (!TF);
			}

			TF = !TF;
		}

		/*
		 *  첫 번째 칸을 기준으로 할 때의 색칠 할 개수(count)와
		 *  첫 번째 칸의 색의 반대되는 색을 기준으로 할 때의
		 *  색칠 할 개수(64 - count) 중 최솟값을 count 에 저장
		 */
		count = Math.min(count, 64 - count);

		/*
		 * 이전까지의 경우 중 최솟값보다 현재 count 값이
		 * 더 작을 경우 최솟값을 갱신
		 */
		min = Math.min(min, count);
	}
}