[백준 문제 풀이] 1018번 체스판 다시 칠하기

Junu Kim·2025년 12월 23일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

66/89

[1018] 체스판 다시 칠하기

난이도: ★★★☆☆ • solved on: 2025-12-23

문제 요약

문제 유형: 완전탐색 (Brute Force), 2D 배열, 구현
요구사항: N×M 보드에서 임의의 8×8 부분을 골라 체스판 패턴(좌상단이 B 시작 또는 W 시작)으로 만들기 위해 다시 칠해야 하는 칸의 최소 개수를 출력해야 한다.

사용 개념

자료구조
- 2차원 배열(String[][])
- 문자열 배열(String[])
알고리즘/기법
- 8×8 모든 부분 보드 탐색
- 두 가지 정답 패턴 (Black-start / White-start) 비교
핵심 키워드
- 마스킹 (masking)
- 패턴 비교 (pattern matching)
- 슬라이딩 윈도우 (window over 2D)

풀이 아이디어

문제 분해

체스판의 올바른 정답 형태는 딱 2개뿐이다.

(1) 좌상단이 B인 체스판

(2) 좌상단이 W인 체스판

따라서 각 8×8 영역마다,

B 시작 패턴으로 만들 때의 변경 수

W 시작 패턴으로 만들 때의 변경 수
를 구해서 더 작은 값을 취하고, 전체 중 최솟값을 갱신하면 된다.
핵심 로직 흐름
for each (top-left) of 8x8:
    count_B_start = mismatches with "B start" pattern
    count_W_start = mismatches with "W start" pattern
    answer = min(answer, min(count_B_start, count_W_start))
예외 처리

i, j 범위는 m-8, n-8 이하(<=) 로 잡아야 8×8 딱 맞는 경우도 검사된다.

코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // "WBWBWBWB" "BWBWBWBW"
        String[] sizes = sc.nextLine().split(" ");
        int n = Integer.parseInt(sizes[1]);
        int m = Integer.parseInt(sizes[0]);
        String[][] sample =  new String[m][n];
        String[] line = new String[n];
        int result = -1;
        for(int i = 0; i < m; i++){
            line = sc.nextLine().split("");
            for(int j = 0; j < n; j++){
                sample[i][j] = line[j];
            }
        }
        String[] rowBlack =  "BWBWBWBW".split("");
        String[] rowWhite =  "WBWBWBWB".split("");

        for(int i =0; i <= m-8; i++){
            for(int j =0; j <= n-8; j++){
                int[][] changes = new int[2][8];
                for(int k = 0; k < 8; k++){
                    for(int l = 0; l < 8; l++){
                        if(!sample[k+i][l+j].equals(rowBlack[l])){
                            changes[k%2][k] += 1;
                        } else {
                            changes[k%2][k] += 0;
                        }
                        if(!sample[k+i][l+j].equals(rowWhite[l])){
                            changes[(k+1)%2][k] += 1;
                        } else {
                            changes[(k+1)%2][k] += 0;
                        }
                    }
                }
                int tmp = Math.min(Arrays.stream(changes[0]).sum(), Arrays.stream(changes[1]).sum());
                if(result == -1){
                    result = tmp;
                } else {
                    result = Math.min(result, tmp);
                }
            }
        }
        System.out.println(result);
    }
}