백준 1018번 - 체스판 다시 칠하기

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

 

풀이 방법

1. 가능한 모든 8x8 구간을 탐색

• (0, 0)부터 시작하여 (N-8, M-8)까지 순회
• 각 시작 좌표에서 8x8 크기 체스판을 자른다.

2. 두 가지 색 시작 케이스를 모두 고려

• 왼쪽 위가 'B'라고 가정하고 고쳐야 하는 칸 수
• 왼쪽 위가 'W'라고 가정하고 고쳐야 하는 칸 수

3. (x + y) % 2를 이용한 패턴 비교

• (x + y) % 2 == 0: 시작 색
• (x + y) % 2 == 1: 반대 색

전체 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int row = sc.nextInt();
		int col = sc.nextInt();
		sc.nextLine(); // 개행 제거
		
		char[][] board = new char[row][col];
		
		// 보드 입력 받기
		for (int i = 0; i < row; i++) {
			String s = sc.nextLine();
			for (int j = 0; j < col; j++) {
				board[i][j] = s.charAt(j);
			}
		}
	
		int answer = Integer.MAX_VALUE;
		
		// 가능한 모든 8x8 체스판 탐색
		for (int i = 0; i <= row - 8; i++) {
			for (int j = 0; j <= col - 8; j++) {
				int countB = 0, countW = 0;

				// 8x8 내부 검사
				for (int x = 0; x < 8; x++) {
					for (int y = 0; y < 8; y++) {
						char current = board[i + x][j + y];

						if ((x + y) % 2 == 0) {
							if (current != 'B') countB++;
							if (current != 'W') countW++;
						} else {
							if (current != 'W') countB++;
							if (current != 'B') countW++;
						}
					}
				}

				// 두 경우 중 최소값 갱신
				answer = Math.min(answer, Math.min(countB, countW));
			}
		}
		
		System.out.print(answer);
		sc.close();
	}
}