시리즈 톺아보기

백준 알고리즘

체스판 다시 칠하기

조건
문제
입력
출력
케이스

예제 1
예제 2

풀이
전체 소스
분류

체스판 다시 칠하기 🔗

랭크	사용 언어

🔗 전체 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 🔗

입력

0 8 8
1 WBWBWBWB
2 BWBWBWBW
3 WBWBWBWB
4 BWBBBWBW
5 WBWBWBWB
6 BWBWBWBW
7 WBWBWBWB
8 BWBWBWBW

출력

0 1

예제 2 🔗

입력

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

출력

0 12

풀이 🔗

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

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

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

JAVA

0 for (int n = 0; n < N - 7; n++)
1 {
2     for (int m = 0; m < M - 7; m++)
3     {
4         // TODO
5     }
6 }

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

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

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

JAVA

0 // 상단 좌측이 하얀색으로 시작하는 체스판
1 private static final boolean[][] WHITE = {
2         { true, false, true, false, true, false, true, false },
3         { false, true, false, true, false, true, false, true },
4         { true, false, true, false, true, false, true, false },
5         { false, true, false, true, false, true, false, true },
6         { true, false, true, false, true, false, true, false },
7         { false, true, false, true, false, true, false, true },
8         { true, false, true, false, true, false, true, false },
9         { false, true, false, true, false, true, false, true },
10 };
11 
12 // 상단 좌측이 검은색으로 시작하는 체스판
13 private static final boolean[][] BLACK = {
14         { false, true, false, true, false, true, false, true },
15         { true, false, true, false, true, false, true, false },
16         { false, true, false, true, false, true, false, true },
17         { true, false, true, false, true, false, true, false },
18         { false, true, false, true, false, true, false, true },
19         { true, false, true, false, true, false, true, false },
20         { false, true, false, true, false, true, false, true },
21         { true, false, true, false, true, false, true, false },
22 };

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

전체 소스 🔗

JAVA

0 import java.io.BufferedReader;
1 import java.io.BufferedWriter;
2 import java.io.IOException;
3 import java.io.InputStreamReader;
4 import java.io.OutputStreamWriter;
5 import java.util.Arrays;
6 
7 /**
8  * 백준 전체 1018 문제 알고리즘 클래스
9  *
10  * @author RWB
11  * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1018">1018 풀이</a>
12  * @since 2021.06.26 Sat 16:46:20
13  */
14 public class Main
15 {
16     // 상단 좌측이 하얀색으로 시작하는 체스판
17     private static final boolean[][] WHITE = {
18             { true, false, true, false, true, false, true, false },
19             { false, true, false, true, false, true, false, true },
20             { true, false, true, false, true, false, true, false },
21             { false, true, false, true, false, true, false, true },
22             { true, false, true, false, true, false, true, false },
23             { false, true, false, true, false, true, false, true },
24             { true, false, true, false, true, false, true, false },
25             { false, true, false, true, false, true, false, true },
26     };
27     
28     // 상단 좌측이 검은색으로 시작하는 체스판
29     private static final boolean[][] BLACK = {
30             { false, true, false, true, false, true, false, true },
31             { true, false, true, false, true, false, true, false },
32             { false, true, false, true, false, true, false, true },
33             { true, false, true, false, true, false, true, false },
34             { false, true, false, true, false, true, false, true },
35             { true, false, true, false, true, false, true, false },
36             { false, true, false, true, false, true, false, true },
37             { true, false, true, false, true, false, true, false },
38     };
39     
40     // 체스판
41     private static boolean[][] board;
42     
43     /**
44      * 메인 함수
45      *
46      * @param args: [String[]] 매개변수
47      *
48      * @throws IOException 데이터 입출력 예외
49      */
50     public static void main(String[] args) throws IOException
51     {
52         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
53         BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
54         
55         int[] temp = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
56         
57         // 세로 길이
58         int N = temp[0];
59         
60         // 가로 길이
61         int M = temp[1];
62         
63         board = new boolean[N][M];
64         
65         for (int n = 0; n < N; n++)
66         {
67             String[] line = reader.readLine().split("");
68             
69             for (int m = 0; m < M; m++)
70             {
71                 board[n][m] = line[m].equals("W");
72             }
73         }
74         
75         // 결과
76         int result = Integer.MAX_VALUE;
77         
78         // 0 ~ 7까지 총 8칸을 전달하므로 최대값에서 7을 뺀다.
79         for (int n = 0; n < N - 7; n++)
80         {
81             for (int m = 0; m < M - 7; m++)
82             {
83                 int count = solve(n, m);
84                 
85                 // 현재 결과보다 더 작은 수일 경우
86                 if (result > count)
87                 {
88                     result = count;
89                 }
90             }
91         }
92         
93         writer.write(Integer.toString(result));
94         writer.newLine();
95         writer.close();
96         reader.close();
97     }
98     
99     /**
100      * 새로 덧칠할 칸의 갯수 반환 함수
101      *
102      * @param x: [int] x의 시작좌표
103      * @param y: [int] y의 시작좌표
104      *
105      * @return [int] 새로 덧칠할 칸의 갯수
106      */
107     private static int solve(int x, int y)
108     {
109         int white = 0;
110         int black = 0;
111         
112         for (int n = x; n < x + 8; n++)
113         {
114             for (int m = y; m < y + 8; m++)
115             {
116                 // 하얀색으로 시작하는 체스판과 색이 다를 경우
117                 if (board[n][m] != WHITE[n - x][m - y])
118                 {
119                     white++;
120                 }
121                 
122                 // 검은색으로 시작하는 체스판과 색이 다를 경우
123                 if (board[n][m] != BLACK[n - x][m - y])
124                 {
125                     black++;
126                 }
127             }
128         }
129         
130         // 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
131         return Math.min(white, black);
132     }
133 }

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

입력

0 8 8
1 BBWBWBWB
2 BWBWBWBW
3 WBWBWBWB
4 BWBWBWBW
5 WBWBWBWB
6 BWBWBWBW
7 WBWBWBWB
8 BWBWBWBW

출력

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

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

JAVA

0 /**
1  * 새로 덧칠할 칸의 갯수 반환 함수
2  *
3  * @param x: [int] x의 시작좌표
4  * @param y: [int] y의 시작좌표
5  *
6  * @return [int] 새로 덧칠할 칸의 갯수
7  */
8 private static int solve(int x, int y)
9 {
10     int white = 0;
11     int black = 0;
12     
13     for (int n = x; n < x + 8; n++)
14     {
15         for (int m = y; m < y + 8; m++)
16         {
17             // 하얀색으로 시작하는 체스판과 색이 다를 경우
18             if (board[n][m] != WHITE[n - x][m - y])
19             {
20                 white++;
21             }
22             
23             // 검은색으로 시작하는 체스판과 색이 다를 경우
24             if (board[n][m] != BLACK[n - x][m - y])
25             {
26                 black++;
27             }
28         }
29     }
30     
31     // 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
32     return Math.min(white, black);
33 }

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

분류 🔗

브루트포스 알고리즘

📆 작성일

2021-06-26 Sat 16:46:20

📚 카테고리

알고리즘

🏷️ 태그

백준

알고리즘

JAVA(자바)

SILVER

SILVER V

Brute Force(무차별 대입 공격)

[백준 / JAVA] 백준 알고리즘 1017번 소수 쌍

[백준 / JAVA] 백준 알고리즘 1019번 책 페이지

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

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

posts

알고리즘

시리즈 톺아보기

Table of Contents

체스판 다시 칠하기 🔗

조건 🔗

문제 🔗

입력 🔗

출력 🔗

케이스 🔗

예제 1 🔗

예제 2 🔗

풀이 🔗

전체 소스 🔗

분류 🔗

0	8 8
1	WBWBWBWB
2	BWBWBWBW
3	WBWBWBWB
4	BWBBBWBW
5	WBWBWBWB
6	BWBWBWBW
7	WBWBWBWB
8	BWBWBWBW

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

0	for (int n = 0; n < N - 7; n++)
1	{
2	for (int m = 0; m < M - 7; m++)
3	{
4	// TODO
5	}
6	}

0	// 상단 좌측이 하얀색으로 시작하는 체스판
1	private static final boolean[][] WHITE = {
2	{ true, false, true, false, true, false, true, false },
3	{ false, true, false, true, false, true, false, true },
4	{ true, false, true, false, true, false, true, false },
5	{ false, true, false, true, false, true, false, true },
6	{ true, false, true, false, true, false, true, false },
7	{ false, true, false, true, false, true, false, true },
8	{ true, false, true, false, true, false, true, false },
9	{ false, true, false, true, false, true, false, true },
10	};
11
12	// 상단 좌측이 검은색으로 시작하는 체스판
13	private static final boolean[][] BLACK = {
14	{ false, true, false, true, false, true, false, true },
15	{ true, false, true, false, true, false, true, false },
16	{ false, true, false, true, false, true, false, true },
17	{ true, false, true, false, true, false, true, false },
18	{ false, true, false, true, false, true, false, true },
19	{ true, false, true, false, true, false, true, false },
20	{ false, true, false, true, false, true, false, true },
21	{ true, false, true, false, true, false, true, false },
22	};

0	import java.io.BufferedReader;
1	import java.io.BufferedWriter;
2	import java.io.IOException;
3	import java.io.InputStreamReader;
4	import java.io.OutputStreamWriter;
5	import java.util.Arrays;
6
7	/**
8	* 백준 전체 1018 문제 알고리즘 클래스
9	*
10	* @author RWB
11	* @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1018">1018 풀이</a>
12	* @since 2021.06.26 Sat 16:46:20
13	*/
14	public class Main
15	{
16	// 상단 좌측이 하얀색으로 시작하는 체스판
17	private static final boolean[][] WHITE = {
18	{ true, false, true, false, true, false, true, false },
19	{ false, true, false, true, false, true, false, true },
20	{ true, false, true, false, true, false, true, false },
21	{ false, true, false, true, false, true, false, true },
22	{ true, false, true, false, true, false, true, false },
23	{ false, true, false, true, false, true, false, true },
24	{ true, false, true, false, true, false, true, false },
25	{ false, true, false, true, false, true, false, true },
26	};
27
28	// 상단 좌측이 검은색으로 시작하는 체스판
29	private static final boolean[][] BLACK = {
30	{ false, true, false, true, false, true, false, true },
31	{ true, false, true, false, true, false, true, false },
32	{ false, true, false, true, false, true, false, true },
33	{ true, false, true, false, true, false, true, false },
34	{ false, true, false, true, false, true, false, true },
35	{ true, false, true, false, true, false, true, false },
36	{ false, true, false, true, false, true, false, true },
37	{ true, false, true, false, true, false, true, false },
38	};
39
40	// 체스판
41	private static boolean[][] board;
42
43	/**
44	* 메인 함수
45	*
46	* @param args: [String[]] 매개변수
47	*
48	* @throws IOException 데이터 입출력 예외
49	*/
50	public static void main(String[] args) throws IOException
51	{
52	BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
53	BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
54
55	int[] temp = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
56
57	// 세로 길이
58	int N = temp[0];
59
60	// 가로 길이
61	int M = temp[1];
62
63	board = new boolean[N][M];
64
65	for (int n = 0; n < N; n++)
66	{
67	String[] line = reader.readLine().split("");
68
69	for (int m = 0; m < M; m++)
70	{
71	board[n][m] = line[m].equals("W");
72	}
73	}
74
75	// 결과
76	int result = Integer.MAX_VALUE;
77
78	// 0 ~ 7까지 총 8칸을 전달하므로 최대값에서 7을 뺀다.
79	for (int n = 0; n < N - 7; n++)
80	{
81	for (int m = 0; m < M - 7; m++)
82	{
83	int count = solve(n, m);
84
85	// 현재 결과보다 더 작은 수일 경우
86	if (result > count)
87	{
88	result = count;
89	}
90	}
91	}
92
93	writer.write(Integer.toString(result));
94	writer.newLine();
95	writer.close();
96	reader.close();
97	}
98
99	/**
100	* 새로 덧칠할 칸의 갯수 반환 함수
101	*
102	* @param x: [int] x의 시작좌표
103	* @param y: [int] y의 시작좌표
104	*
105	* @return [int] 새로 덧칠할 칸의 갯수
106	*/
107	private static int solve(int x, int y)
108	{
109	int white = 0;
110	int black = 0;
111
112	for (int n = x; n < x + 8; n++)
113	{
114	for (int m = y; m < y + 8; m++)
115	{
116	// 하얀색으로 시작하는 체스판과 색이 다를 경우
117	if (board[n][m] != WHITE[n - x][m - y])
118	{
119	white++;
120	}
121
122	// 검은색으로 시작하는 체스판과 색이 다를 경우
123	if (board[n][m] != BLACK[n - x][m - y])
124	{
125	black++;
126	}
127	}
128	}
129
130	// 둘 중 더 적게 칠할 수 있는 체스판의 값을 반환
131	return Math.min(white, black);
132	}
133	}

0	8 8
1	BBWBWBWB
2	BWBWBWBW
3	WBWBWBWB
4	BWBWBWBW
5	WBWBWBWB
6	BWBWBWBW
7	WBWBWBWB
8	BWBWBWBW