👀 문제
https://www.acmicpc.net/problem/1018
👊 도전
풀이 방법 1
1. 설계
- 가능한 모든 8*8크기의 체스판을 만들어 검은색, 흰색으로 번갈아 칠하려면 몇 개를 바꾸어야 하는지 센다.
- 맨 처음이 흰색인 경우, 검은색인 경우 두 가지를 모두 구해야하지만, 한 경우만 구하면 나머지 하나도 알 수 있다. 처음이 흰색으로 시작했을 때 다시 칠해야하는 갯수가 n이라면 검은색으로 시작했을 때는 64-n이다.
- 다시 칠해야하는 정사각형의 최소 갯수를 리턴한다.
2. 구현 (성공 코드)
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
import java.util.Scanner;
/**
*
* @author HEESOO
*
*/
public class Main {
public static int min(char[][] board, int x, int y){
String[] color={"WBWBWBWB","BWBWBWBW"};
int cnt=0, ii=0, jj=0;
for(int i=x;i<x+8;i++){
ii=i%2;
for(int j=y;j<y+8;j++){
jj=j-y;
if(board[i][j]!=color[ii].charAt(jj)){
cnt++;
}
}
}
if(cnt>32) cnt=64-cnt;
return cnt;
}
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int m=input.nextInt();
char[][] board=new char[n][m];
String str;
for(int i=0;i<n;i++){
str=input.next();
for(int j=0;j<m;j++){
board[i][j]=str.charAt(j);
}
}
int answer=64, temp;
for(int i=0;i<n-7;i++){
for(int j=0;j<m-7;j++){
temp=min(board, i, j);
if(answer>temp) answer=temp;
}
}
System.out.println(answer);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 2중for문으로 가능한 8*8크기를 찾는다.
- 해당 크기의 시작점 i, j를 파라미터로 min()함수를 실행한 후, 리턴값 중 최솟값만 answer에 저장한다.
- 체스판을 만들기 위해 몇 개를 다시 칠해야하는지 센다.
- 한 줄은 흰색 또는 검은색으로 시작하는 두 방법 밖에 없다.
- x, y로 넘겨받은 시작점을 가지고 만드는 체스판은 시작점 x가 짝수 홀수에 따라 시작하는 색깔이 결정된다. ii는 color[0], color[1]을 선택하기 위함이다.
- 처음 for문에서 어떤 줄과 비교할지 color[ii]가 결정되었다면, jj는 color[ii]안에서 char형으로 문자를 뽑아내어 비교한다. 이때 시작점 y에서부터 8개를 비교해야하고, jj는 0~7까지의 범위이므로 jj=j-y로 범위를 맞춘다.
- 위의 2중for문을 수행하면 맨 처음이 흰색 또는 검은색으로 시작하는 체스판을 만들기 위해 다시 칠해야하는 갯수 n을 알 수 있다. 반대로 검은색 또는 흰색으로 칠하는 경우는 64-n과 같다. 색깔을 다시 뒤집으면 되기 때문이다. 이중 작은 값을 리턴하면 된다.
👏 해결 완료!
참고
- [백준 - 1018번] 체스판 다시 칠하기 - Java //Wello Horld// https://wellohorld.tistory.com/41