[백준] 1018 체스판 다시 칠하기 자바

문제출처: https://www.acmicpc.net/problem/1018

접근

문제만 잘 읽어본다면, 손쉽게 이해할 수 있는 문제였습니다.
문제에 체스판을 색칠하는 경우는 총 2가지.--> 맨왼쪽위 흰색 || 검은색
즉, 체스판을 만들기 위해서는 한 칸 기준으로 상하좌우의 색이 다르면 된다.
또한, 체스판이 잘못 칠해질 경우도 생각해야한다. --> 최소 개수로 칠할 수 있는 부분을 생각하면된다.

경우의수

(가로칸 개수-7) x (세로칸개수 -7)이다.
--> 이유 : 최소크기가 8x8일 때, 경우의 수가 1이기 때문에 각변에는 -7을 해줘야한다.
따라서, 앞서 말했듯이 체스판을 색칠하는 경우는 총 2가지였다.
따라서 2를 곱해주면 끝이다. --> 이것은 2를 곱해서 사용하거나 반복문을 2번 돌리면 해결되는 것이다.

코드

필자가 처음 접근한 방법은 dfs다.

--> 이유? -->없다.
필자는 요즘 dfs에 빠졌기 때문에, 모든 문제를 일단 dfs로 구현하고 본다.

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

public class Main {
    static String[] board;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        board = new String[n];

        for (int i = 0; i < n; i++) {
            board[i] = br.readLine();
        }

        dfs(0, 0, n, m);

        System.out.println(min);
    }

    public static void dfs(int x, int y, int n, int m) {
        if (x + 7 < n && y + 7 < m) {
            calculateMinChanges(x, y);
            dfs(x + 1, y, n, m);
            dfs(x, y + 1, n, m);
        }
    }

    public static void calculateMinChanges(int startX, int startY) {
        int cnt1 = 0;
        int cnt2 = 0;
        char[] colors = {'B', 'W'};
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[startX + i].charAt(startY + j) != colors[(i + j) % 2]) {
                    cnt1++;
                } else {
                    cnt2++;
                }
            }
        }
        min = Math.min(min, Math.min(cnt1, cnt2));
    }
}

기본

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] board = new int[n][m];

        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = line.charAt(j);
            }
        }

        int min = Integer.MAX_VALUE;

        for (int i = 0; i < n - 7; i++) {
            for (int j = 0; j < m - 7; j++) {
                int cnt1 = 0;
                int cnt2 = 0;
                for (int k = 0; k < 8; k++) {
                    for (int l = 0; l < 8; l++) {
                        if ((k + l) % 2 == 0) { 
                            if (board[i + k][j + l] == 'B') cnt1++;
                            else cnt2++;
                        } else { 
                            if (board[i + k][j + l] == 'W') cnt1++;
                            else cnt2++;
                        }
                    }
                }
                min = Math.min(min, Math.min(cnt1, cnt2));
            }
        }

        System.out.println(min);
    }
}