지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[][] array = new int[50][50];
// 1. 배열 입력
for (int i = 0; i < N; i++) {
String s = sc.next();
for (int j = 0; j < M; j++) {
if (s.charAt(j) == 'W') {
array[i][j] = 1;
} else {
array[i][j] = 2;
}
}
}
// 2. 체스 정답 입력
int[][] answer1 = new int[8][8];
int[][] answer2 = new int[8][8];
int[] pattern1 = { 1, 2, 1, 2, 1, 2, 1, 2 };
int[] pattern2 = { 2, 1, 2, 1, 2, 1, 2, 1 };
for (int i = 0; i < 8; i++) {
if (i % 2 == 0) { // 짝수번째 인덱스
answer1[i] = pattern1;
answer2[i] = pattern2;
} else {
answer1[i] = pattern2;
answer2[i] = pattern1;
}
}
// 3. 체스판 찾기
int row = N-7;
int col = M-7;
int mini = 64;
for(int k = 0; k < row; k++) {
for(int p = 0; p < col; p++) {
int sum1 = 0;
int sum2 = 0;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (array[i+k][j+p] != answer1[i][j]) {
sum1 += 1;
}
if(array[i+k][j+p] != answer2[i][j]) {
sum2 += 1;
}
}
}
int temp = Math.min(sum1, sum2);
mini = Math.min(mini, temp);
}
}
System.out.println(mini);
}
}
풀이
1. 배열 입력
이 부분은 말 그대로 보드를 입력받는 부분이다. 이 코드 위에 N과 M을 입력받는 부분도 있다.
sc.next()를 이용해서 한 줄을 s에 저장하고 W면 1로, B면 2로 array에 저장해주었다.
2. 체스 정답 입력
이 문제는 무조건 확인할 때 8x8로 확인하고, 체스판이 될 수 있는 경우의 수가 2가지(맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우)이기 때문에 정답이 될 수 있는 경우를 answer1과 answer2로 나누어 저장해주었다.
즉 answer1은 아래와 같고, answer2는 맨 왼쪽 위 칸이 2로 시작할 것이다.
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
| 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
| 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
| 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
| 1 | 2 | 1 | 2 | 1 | 2 | 1 | 2 |
| 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 |
이렇게 저장한 answer1과 answer2를 가지고 입력받은 보드 위에 돌리면서 비교해 서로 다른 숫자의 개수를 세고 최솟값을 출력한다.
3. 체스판 찾기
만약 주어진 보드가 10x10 크기라면 8x8 크기인 answer1이 몇 개 돌릴 수 있을까?
간단하게 0~9까지 총 10칸이 있다고 생각하면 0~7, 1~8, 2~9 총 3개의 8칸을 돌릴 수 있다.
즉 10x10 크기로 생각하면 3 x 3 = 9 개의 체스판을 확인하게 된다.
만약 11x11이라면? 4x4 = 16 개의 체스판을 확인하게 된다. (이때 체스판은 문제에서 8x8로 자른다고 명시되어있다)
여기서 규칙을 알 수 있다. (주어진 보드 길이의 row - 3 ) x (주어진 보드 길이의 col - 3) 만큼의 체스판을 확인한다는 사실이다.
주어진 보드판이 10x10이면 배열로 생각했을 때 [0][0]부터 [9][9]까지 존재한다.
따라서 8x8인 answer1과 answer2와 보드를 8x8로 잘라서 비교하고, 틀린 것의 개수를 비교할 때마다 구해서 제일 작은 값을 출력한다. 10x10 보드를 8x8로 자른다면 위에 구했듯이 총 9번을 비교하게 될 것이다.
[0][0]~[7][7]을 시작으로 [2][2]~[9][9]까지 이동할 것이다. (맨 왼쪽 위 ~ 맨 오른쪽 아래)
k와 p가 전체 8x8을 이동시키는 for문이 되고, i와 j가 8x8을 직접 탐색하는 for문이 된다.
i와 j의 이중 포문 안에서는 보드와 answer1을 비교해 값이 다르면 sum1에 1을 더해주고, 보드와 answer2를 비교해 값이 다르면 sum2에 1을 더해준다. 값이 다르다는 건 정답인 answer와 다른 부분인 것이고, 즉 체스판이 되기 위해서 다시 칠해야 하는 부분인 것이다. array에서 k과 p를 더해주는 이유는 처음에 입력받은 보드를 8x8 크기로 잘라줄 때 이동시키기 위해서이다.
이때 sum1과 sum2는 8x8 비교를 한 번 할 때마다 구하므로 i 포문 위에서 0으로 계속 초기화시켜준다. 한 번의 비교 후에는 최솟값을 구해준다. Math.min 함수는 괄호 안의 두 값 중 최솟값을 반환해준다. mini가 64인 이유는 최대로 체스판을 만들기 위해 색칠하는 횟수가 64이기 때문이다.
'Algorithm > 백준' 카테고리의 다른 글
| [백준][Python] 13251. 조약돌 꺼내기 (0) | 2022.03.14 |
|---|---|
| [백준][Java] 2750. 수 정렬하기 (0) | 2022.03.08 |
| [백준][Java] 10989. 수 정렬하기 3 (0) | 2022.03.07 |
| [백준][Python] 1436. 영화감독 숌 (2) | 2022.03.05 |
| [백준][Python] 15881. Pen Pineapple Apple Pen (0) | 2022.03.05 |
