B1018 체스판 다시 칠하기
| 날짜 | 2024-04-01 |
| 사용 언어 | Java |
| 문제 유형 | 브루트포스 알고리즘 |
| 문제 URL | https://www.acmicpc.net/problem/1018 |
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 120830 | 59968 | 47955 | 49.794% |
문제 #
문제 설명 #
지민이는 자신의 저택에서 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) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
sc.nextLine(); // 개행문자 삭제
// 주어진 보드
String[] row = new String[N];
for (int i = 0; i < N; i++) {
row[i] = sc.nextLine();
}
int min = 32; // 최대 32 ( 전부 W거나 B )
// 8 * 8 당 필요한 색칠 횟수 구하기 (체스판의 개수만큼 반복)
//총 체스판의 개수 = (N-7) * (M-7)
for (int i = 0; i <= N - 8; i++) {
for (int j = 0; j <= M - 8; j++) {
int count = 0;
count = differ(row, i, j);
// min보다 count가 작을 경우 min = count;
if (min > count) {
min = count;
}
}
}
System.out.println(min);
}
private static int differ(String[] row, int startRow, int startCol) {
// W로 시작 할 경우
int countW = 0;
for (int i = startRow; i < startRow + 8; i++) {
for (int j = startCol; j < startCol + 8; j++) {
// 짝+짝, 홀+홀 짝수, 짝+홀 홀수
char wb = (i + j) % 2 == 0 ? 'W' : 'B';
if (row[i].charAt(j) != wb) {
countW++;
}
}
}
// B로 시작 할 경우
int countB = 0;
for (int i = startRow; i < startRow + 8; i++) {
for (int j = startCol; j < startCol + 8; j++) {
// 짝+짝, 홀+홀 짝수, 짝+홀 홀수
char wb = (i + j) % 2 == 0 ? 'B' : 'W';
if (row[i].charAt(j) != wb) {
countB++;
}
}
}
return Math.min(countW, countB);
}
}
- 기존 코드
- countB 부분 삭제 및 64 - count 이용 시
다른 사람의 풀이 #
// 최소값 찾는 부분
public static int solve(boolean matrix[][], int x, int y) {
int chessX == x + 8;
int chessY == y + 8;
int count = 0;
boolean curColor = matrix[x][y];
for (int i = x; i < chessX; i++) {
for (int j = y; j < chessY; j++) {
// 예상 색과 다를 경우 count
if (matrix[i][j] != curColor) {
count++;
}
// 다음 칸의 색 예측
curColor = (!curColor);
}
// 행이 바뀌면 다시 반전 (1행의 마지막 == 2행의 처음)
curColor = (!curColor);
}
// 최악의 case 는 64
// 첫 행이 W일때랑 B는 정 반대의 결과를 보여주기때문에 64-count
return Math.min(count, 64 - count);
}