[백준 | Java] 1018번 체스판 다시 칠하기

1018번 / 체스판 다시 칠하기

❓ 체스판 다시 칠하기

🏷️ 관련 주제 : 브루트포스 알고리즘

💦 나의 시도

N × M 크기의 보드 왼쪽 상단부터 검은색(1)으로 칠한다고 가정하고
칠할 색과 보드의 색이 일치하면 칠하지 않아도 됨.
이것을 빼기로 계산하였습니다.

 

보드 색	칠할 색	일치 여부
검은색 (1)	검은색 (1)	일치 (1 - 1 = 0)
검은색 (1)	흰색 (0)	불일치 (1 - 0 = 1)
흰색 (0)	검은색 (1)	불일치 (0 - 1 = -1)
흰색 (0)	흰색 (0)	일치 (0 - 0 = 0)

위의 표를 보면 일치할 때는 두 수의 차의 절댓값이 1인 것을 확인할 수 있습니다.
이 절댓값을 이차원 배열 int[][] board에 저장하였고

출력할 결과값 int minCnt를 32로 초기화하였습니다.
(처음에 64로 초기화 했는데

이 경우, 반대로 왼쪽 상단을 흰색부터 칠하면 한개도 칠하지 않아도 되므로

32로 초기화 해 주었습니다.)

 

0 ~ N - 8 범위, 0 ~ M - 8 범위를 이중 for문을 돌리고
여기에 반복문의 int 변수 i, j를 왼쪽 상단으로 하는 체크 보드에서 칠해야할 개수를 구하였습니다.

먼저 int cnt를 0으로 초기화하고 다시 2중 for문을 돌렸습니다.
(사실 여기서 4중 for문을 돌리는 것이 괜찮을까? 살짝 고민이 되었는데
일단 코드를 써 보고 실패하면 수정하자는 생각으로 시도해 본 결과 실행 성공하였습니다.
N과 M이 8 이상 50 이하의 자연수로 범위가 크지 않아
42 × 42 × 8 × 8 = 112,896로 실행 성공할 수 있었던 것 같습니다.)

cnt에 board의 해당 인덱스 값을 더해 주었고

그 결과가 32보다 크면 색을 반전하는 경우가 더 덜 색칠해도 되므로 cnt에 64 - cnt를 할당해 주었습니다.

그리고 minCnt와 값을 비교하여 cnt와 minCnt 중 더 작은 값을 minCnt에 재할당 해 주었습니다.

4중 for문 완료 후, minCnt값을 출력해 주었습니다.

 

맞았습니다!!

• 메모리 : 14208 KB
• 시간 : 108 ms
• 코드 길이 : 1521 B

📑제출 기록 및 오답 원인

처음 제출도 성공하였지만 minCnt의 초기값을 64로 주었었는데 32로 주는 게 더 적절한 것 같아 다시 제출하였습니다.

💯 해결 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] board = new int[N][M];

        for (int i = 0; i < N; i++) {
            String row = br.readLine();

            for (int j = 0; j < M; j++) {
                char c = row.charAt(j);
                int color = 0;

                if (c == 'B') {
                    color = 1;
                }

                if ((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
                    color -= 1;
                }

                board[i][j] = Math.abs(color);
            }
        }

        int minCnt = 32;

        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                int cnt = 0;
                for (int i2 = i; i2 < i + 8; i2++) {
                    for (int j2 = j; j2 < j + 8; j2++) {
                        cnt += board[i2][j2];
                    }
                }

                if (cnt > 32) {
                    cnt = 64 - cnt;
                }
                minCnt = Math.min(cnt, minCnt);
            }
        }

        System.out.println(minCnt);
    }
}