체스판 다시 칠하기

---

🔗 🔗 전체 1018번 문제

조건

---

문제

---

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

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

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

입력

---

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

출력

---

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

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
5
6
7
8
9
8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• 출력

TC
1
1

예제 2

---

• 입력

TC
1
2
3
4
5
6
7
8
9
10
11
10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

• 출력

TC
1
12

풀이

---

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

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

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

JAVA
1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 상단 좌측이 하얀색으로 시작하는 체스판
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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
1
2
3
4
5
6
7
8
9
8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

• 출력

1

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

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

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 새로 덧칠할 칸의 갯수 반환 함수
 *
 * @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을 만드는데 필요한 칸의 숫자를 각각 구해서, 그 중 더 작은 수를 반환해야 올바르게 동작한다.

분류

---

• 브루트포스 알고리즘