[CLASS 2: 브루트포스] 백준 1018 체스판 다시 칠하기

1018번: 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018

 

# 코드

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

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()); // 가로 크기

        char[][] board = new char[n][m]; // 입력받은 체스판
        for (int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray(); // 각 줄을 한 글자씩 배열에 저장
        }

        int minPaint = Integer.MAX_VALUE;

        // 8x8 체스판을 모든 가능한 위치에서 검사
        for (int i = 0; i <= n - 8; i++) {
            for (int j = 0; j <= m - 8; j++) {
                int cntW = 0; // 첫 칸이 'W'로 시작하는 체스판을 다시 칠해야 하는 횟수
                int cntB = 0; // 첫 칸이 'B'로 시작하는 체스판을 다시 칠해야 하는 횟수

                // 8x8 부분 체스판 검사
                for (int x = 0; x < 8; x++) {
                    for (int y = 0; y < 8; y++) {
                        // 현재 8x8 체스판의 (x, y) 위치의 색
                        char current = board[i + x][j + y];

                        // 체스판의 규칙에 맞는 색상 계산
                        if ((x + y) % 2 == 0) {
                            // 짝짝, 홀홀인 위치
                            if (current != 'W') cntW++; // 첫 칸이 'W'로 시작했을 때 B이면 다시 칠함
                            if (current != 'B') cntB++; // 첫 칸이 'B'로 시작했을 때 W이면 다시 칠함
                        } else {
                            // 짝홀, 홀짝인 위치
                            if (current != 'B') cntW++; // 첫 칸이 'W'로 시작했을 때 B이면 다시 칠함
                            if (current != 'W') cntB++; // 첫 칸이 'B'로 시작했을 때 W이면 다시 칠함
                        }
                    }
                }

                // 최소값 갱신
                minPaint = Math.min(minPaint, Math.min(cntW, cntB));
            }
        }

        System.out.println(minPaint); // 최종 결과 출력
        br.close();
    }
}

• 먼저 입력받은 체스판의 크기 n과 m을 기준으로 2차원 배열 board를 만들고, 각 칸에 있는 값을 저장한다. 각 줄은 문자열로 주어지기 때문에 toCharArray()를 이용해 한 글자씩 배열에 저장한다.
• 여기서 i와 j는 각각 세로와 가로에서 8x8 크기의 체스판을 어디서부터 시작할지를 결정하는 좌표이다.
  • i <= n - 8 및 j <= m - 8 조건을 사용해 체스판의 끝을 넘지 않도록 8x8 체스판을 선택할 수 있다.
  • 각각의 8x8 체스판에 대해 첫 칸이 'W'로 시작하는 경우와 'B'로 시작하는 경우를 모두 고려해서, 다시 칠해야 할 칸의 개수를 계산할 것이다.
• x와 y는 선택된 8x8 체스판 내에서의 위치이다. 즉, i와 j로 8x8 체스판의 시작점을 정한 후, 그 안에서 x와 y는 8x8 칸 내의 각 칸을 돌며 그 칸의 색을 비교한다.
• (x + y) % 2 == 0은 짝짝 또는 홀홀인 좌표, 즉 동일한 색이 나와야 하는 위치를 의미한다.
  • 첫 칸이 'W'로 시작하면 그 자리에 'W'가 있어야 하지만 'B'가 있다면 cntW를 증가시킨다.
  • 첫 칸이 'B'로 시작하면 그 자리에 'B'가 있어야 하지만 'W'가 있다면 cntB를 증가시킨다.
• (x + y) % 2 != 0은 짝홀 또는 홀짝인 좌표, 즉 다른 색이 나와야 하는 위치를 의미한다.
  • 첫 칸이 'W'로 시작하면 그 자리에 'B'가 있어야 하지만 'W'가 있다면 cntW를 증가시킨다.
  • 첫 칸이 'B'로 시작하면 그 자리에 'W'가 있어야 하지만 'B'가 있다면 cntB를 증가시킨다.
• 마지막으로 현재 선택된 8x8 체스판에서 첫 칸이 'W'일 때(cntW)와 'B'일 때(cntB) 중 더 적은 칸을 다시 칠하는 경우를 선택하고, 그 값이 현재 최소값보다 작으면 갱신하면 된다.