🔗 Full Problem 1018

Jimin found a board of size $M \times N$, divided into $MN$ unit squares, in his mansion. Some of the squares are painted black, and the rest are painted white. Jimin wants to cut this board to make an $8 \times 8$ chessboard.

A chessboard must be painted with black and white alternating. Specifically, each square is painted either black or white, and any two squares sharing an edge must be painted a different color. Following this definition, there are only two ways to paint a chessboard: one where the top-left square is white, and one where it's black.

Since there's no guarantee the board is already painted like a chessboard, Jimin thought that after cutting out an $8 \times 8$ chessboard, he might need to repaint some of the squares. Of course, the $8 \times 8$ section can be chosen from anywhere on the board. Write a program to find the minimum number of squares Jimin needs to repaint.

The first line gives $N$ and $M$. $N$ and $M$ are natural numbers greater than or equal to 8 and less than or equal to 50. From the second line, $N$ lines follow, giving the state of each row of the board. B stands for black, and W stands for white.

On the first line, print the minimum number of squares Jimin needs to repaint.

• Input

TC
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• Output

TC
1

• Input

TC
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

• Output

TC
12

From a large board with each square painted white or black, we need to cut out an $8 \times 8$ chessboard starting at an arbitrary position. Among all possible positions, we want to find the minimum number of squares we'd need to repaint to form a valid chessboard. Given how small the constraint ranges are, we can just brute-force compare every possibility one by one.

As shown above, we need to extract an $8 \times 8$ subarray from every possible position within the $N \times M$ array.

Based on a $10 \times 10$ array, there are a total of 9 ways to select an $8 \times 8$ subarray from that board, as diagrammed above. Likewise, we just need to slide an $8 \times 8$ window across the entire array one square at a time and compare each position.

JAVA
for (int n = 0; n < N - 7; n++)
{
	for (int m = 0; m < M - 7; m++)
	{
		// TODO
	}
}

Writing it as shown above moves one square at a time horizontally, and once it reaches the end, moves down one row vertically before moving horizontally again from the start. The reason it's n < N - 7 is that the array being compared has a height of 8. If that's slightly confusing, you can replace it with n <= N - 8 instead.

There are two possible cases for a chessboard.

Based on the top-left square of the chessboard, there are two cases: a board starting with white and a board starting with black. We'll represent white as true and black as false, creating a white chessboard and a black chessboard to compare against.

JAVA
// 상단 좌측이 하얀색으로 시작하는 체스판
private static final boolean[][] WHITE = {
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
};

// 상단 좌측이 검은색으로 시작하는 체스판
private static final boolean[][] BLACK = {
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
		{ false, true, false, true, false, true, false, true },
		{ true, false, true, false, true, false, true, false },
};

The code is shown above. For a simple two-way choice like black and white, I generally prefer using boolean, so I designed it this way. It would work just as well using a String array with "W" and "B" values, as long as the comparison logic is done properly. We compare this against every possible $8 \times 8$ window and print the smallest count.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 백준 전체 1018 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1018">1018 풀이</a>
 * @since 2021.06.26 Sat 16:46:20
 */
public class Main
{
	// 상단 좌측이 하얀색으로 시작하는 체스판
	private static final boolean[][] WHITE = {
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
	};
	
	// 상단 좌측이 검은색으로 시작하는 체스판
	private static final boolean[][] BLACK = {
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
			{ false, true, false, true, false, true, false, true },
			{ true, false, true, false, true, false, true, false },
	};
	
	// 체스판
	private static boolean[][] board;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int[] temp = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		// 세로 길이
		int N = temp[0];
		
		// 가로 길이
		int M = temp[1];
		
		board = new boolean[N][M];
		
		for (int n = 0; n < N; n++)
		{
			String[] line = reader.readLine().split("");
			
			for (int m = 0; m < M; m++)
			{
				board[n][m] = line[m].equals("W");
			}
		}
		
		// 결과
		int result = Integer.MAX_VALUE;
		
		// 0 ~ 7까지 총 8칸을 전달하므로 최대값에서 7을 뺀다.
		for (int n = 0; n < N - 7; n++)
		{
			for (int m = 0; m < M - 7; m++)
			{
				int count = solve(n, m);
				
				// 현재 결과보다 더 작은 수일 경우
				if (result > count)
				{
					result = count;
				}
			}
		}
		
		writer.write(Integer.toString(result));
		writer.newLine();
		writer.close();
		reader.close();
	}
	
	/**
	 * 새로 덧칠할 칸의 갯수 반환 함수
	 *
	 * @param x: [int] x의 시작좌표
	 * @param y: [int] y의 시작좌표
	 *
	 * @return [int] 새로 덧칠할 칸의 갯수
	 */
	private static int solve(int x, int y)
	{
		int white = 0;
		int black = 0;
		
		for (int n = x; n < x + 8; n++)
		{
			for (int m = y; m < y + 8; m++)
			{
				// 하얀색으로 시작하는 체스판과 색이 다를 경우
				if (board[n][m] != WHITE[n - x][m - y])
				{
					white++;
				}
				
				// 검은색으로 시작하는 체스판과 색이 다를 경우
				if (board[n][m] != BLACK[n - x][m - y])
				{
					black++;
				}
			}
		}
		
		// 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
		return Math.min(white, black);
	}
}

When I first designed this, I found the color of board[x][y], the top-left value of the cut-out $8 \times 8$ array board, and compared against WHITE when it was white (true) or BLACK when it was black (false) — but that kept giving wrong answers. Looking at the case below makes it easy to understand why.

• Input

TC
8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• Output

TEXT
1

Since the entire board is already $8 \times 8$, there's only one possible window: the board itself. If it worked the way I originally designed it, this case would cause a problem.

In this case, $board[0][0] = false$, so it gets compared against BLACK. That means all 63 remaining squares except $board[0][0]$ would need to be repainted. But look closely at this case again — in fact, all you need to do is repaint just $board[0][0]$ to white (true). In other words, if you compare against WHITE instead of BLACK, the value comes out to 1.

JAVA
/**
 * 새로 덧칠할 칸의 갯수 반환 함수
 *
 * @param x: [int] x의 시작좌표
 * @param y: [int] y의 시작좌표
 *
 * @return [int] 새로 덧칠할 칸의 갯수
 */
private static int solve(int x, int y)
{
	int white = 0;
	int black = 0;
	
	for (int n = x; n < x + 8; n++)
	{
		for (int m = y; m < y + 8; m++)
		{
			// 하얀색으로 시작하는 체스판과 색이 다를 경우
			if (board[n][m] != WHITE[n - x][m - y])
			{
				white++;
			}
			
			// 검은색으로 시작하는 체스판과 색이 다를 경우
			if (board[n][m] != BLACK[n - x][m - y])
			{
				black++;
			}
		}
	}
	
	// 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
	return Math.min(white, black);
}

The solve() method is the core of the algorithm. This is why we compare against both WHITE and BLACK: we compute the number of squares needed to convert the current subarray into WHITE and into BLACK separately, and return whichever is smaller — that's what makes it work correctly.

• Brute Force Algorithm