logo

𝝅번째 알파카의 개발 낙서장

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

게시글
⏰ 2021-06-26 07:46:20

D O W N

https://user-images.githubusercontent.com/50317129/120028591-d5ece480-c02f-11eb-88f0-e14fc647dd81.png
백준 알고리즘
이 게시글은 백준 알고리즘 시리즈의 23개 중 20번 째 게시글입니다.
https://user-images.githubusercontent.com/50317129/260317030-e4b8575b-f09e-47f4-ab70-168a817268c6.png

Table of Contents

https://user-images.githubusercontent.com/50317129/260317030-e4b8575b-f09e-47f4-ab70-168a817268c6.png

체스판 다시 칠하기

랭크사용 언어
JAVA

🔗 🔗 전체 1018번 문제

조건

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

문제

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

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

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

입력

첫째 줄에 NNMM이 주어진다. NNMM은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 NN개의 줄에는 보드의 각 행의 상태가 주어진다. 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×88 \times 8 크기로 잘라 체스판을 만든다. 그 중 가장 적은 칸을 칠하여 체스판을 만들고자 할 때, 칠해야하는 최소값을 구하는 문제. 주어진 변수의 범위가 적어 그냥 무식하게 하나하나 비교하면 된다.

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

10×1010 \times 10짜리 배열을 기준으로, 해당 판에서 8×88 \times 8 배열을 선택하는 경우의 수는 총 9가지이며, 이를 도식화하면 위 그림과 같다. 이처럼 전체 배열에서 8×88 \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×88 \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×88 \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×88 \times 8이므로 경우의 수는 판 자체로 하나다. 만약 처음 설계한대로 동작한다면 위 케이스에서 문제가 발생한다.

위 케이스의 board[0][0]=falseboard[0][0] = false이므로 BLACK과 비교하게 된다. 이러면 board[0][0]board[0][0]를 제외한 나머지 63개의 칸을 전부 칠해야한다. 그런데 저 케이스, 자세히 한 번 보자. 사실 board[0][0]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() 메소드는 알고리즘의 핵심 동작이다. WHITEBLACK을 전부 비교하는 이유가 여기에 있는데, 현재 배열에서 WHITEBLACK을 만드는데 필요한 칸의 숫자를 각각 구해서, 그 중 더 작은 수를 반환해야 올바르게 동작한다.

분류

  • 브루트포스 알고리즘

🏷️ Related Tag

# 백준
# 알고리즘
# JAVA(자바)
# SILVER
# SILVER V
# Brute Force(무차별 대입 공격)

😍 읽어주셔서 감사합니다!
도움이 되셨다면, 💝공감이나 🗨️댓글을 달아주시는 건 어떤가요?
블로그 운영에 큰 힘이 됩니다!
https://blog.itcode.dev/posts/2021/06/26/a1018