[백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8 X 8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

[백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기

@RWBwritten at 2021-06-26 07:46:20

시리즈 모아보기

백준 알고리즘

20 / 23

체스판 다시 칠하기

랭크	사용 언어
	🖼️ JAVA

🔗 전체 1018번 문제

조건

시간제한	메모리 제한
2초	128MB

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 $M \times N$ 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 $8 \times 8$ 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 $8 \times 8$ 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 $8 \times 8$ 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ 과 $M$ 이 주어진다. $N$ 과 $M$ 은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 $N$ 개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

케이스

예제 1

입력

TC
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력

TC
1

예제 2

입력

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

출력

TC
12

풀이

각 칸이 흰색 또는 검은색으로 칠해진 커다란 판에서 임의의 위치부터 $8 \times 8$ 크기로 잘라 체스판을 만든다. 그 중 가장 적은 칸을 칠하여 체스판을 만들고자 할 때, 칠해야하는 최소값을 구하는 문제. 주어진 변수의 범위가 적어 그냥 무식하게 하나하나 비교하면 된다.

위 처럼 $N \times M$ 의 배열에서 무작위 $8 \times 8$ 크기의 배열을 뽑아내야한다.

$10 \times 10$ 짜리 배열을 기준으로, 해당 판에서 $8 \times 8$ 배열을 선택하는 경우의 수는 총 9가지이며, 이를 도식화하면 위 그림과 같다. 이처럼 전체 배열에서 $8 \times 8$ 만큼 한 칸씩 이동하며 비교하면 된다.

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

위 코드와 같이 기술하면 가로부터 한 칸씩 이동하며, 끝에 도달할 경우 세로로 한 칸 이동한 뒤 다시 가로부터 한 칸씩 이동할 것이다. n < N - 7인 이유는 비교할 배열의 세로 길이가 8이기 때문. 살짝 헷갈린다면 n <= N - 8으로 대체해도 무방하다.

체스판에는 두 가지 경우의 수가 있다.

체스판의 상단 좌측을 기준으로 하얀색으로 시작하는 판과, 검은색으로 시작하는 판으로 두 가지가 존재한다. 하얀색을 true, 검은색을 false로 치환하여 하얀색 체스판과 검은색 체스판을 만들어 비교할 것이다.

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 },
};

코드는 위와 같다. 흑백과 같이 이지선다일 경우 boolean을 사용하는 것을 더 선호하므로 위와 같이 설계했다. String 배열로 "W", "B"를 넣어 만들어도 비교만 잘 해준다면 크게 상관없다. 이를 $8 \times 8$ 의 모든 경우의 수와 비교하여 가장 작은 수를 출력하면 된다.

전체 소스

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);
	}
}

처음에 설계했을 땐, 잘라낸 $8 \times 8$ 배열 board의 좌측 상단값인 board[x][y]의 색을 찾아서, 하얀색(true)일 경우 WHITE를, 검은색(false)일 경우 BLACK을 갖고 비교했는데 계속 틀렸다. 아래 케이스를 보면 이해가 쉽다.

입력

TC
8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

출력

TEXT
1

전체 판 자체가 $8 \times 8$ 이므로 경우의 수는 판 자체로 하나다. 만약 처음 설계한대로 동작한다면 위 케이스에서 문제가 발생한다.

위 케이스의 $board[0][0] = false$ 이므로 BLACK과 비교하게 된다. 이러면 $board[0][0]$ 를 제외한 나머지 63개의 칸을 전부 칠해야한다. 그런데 저 케이스, 자세히 한 번 보자. 사실 $board[0][0]$ 만 하얀색(true)로 칠해주면 그만이다. 즉, BLACK이 아닌 WHITE와 비교하면 값이 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);
}

solve() 메소드는 알고리즘의 핵심 동작이다. WHITE와 BLACK을 전부 비교하는 이유가 여기에 있는데, 현재 배열에서 WHITE와 BLACK을 만드는데 필요한 칸의 숫자를 각각 구해서, 그 중 더 작은 수를 반환해야 올바르게 동작한다.

[백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기