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

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

 

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

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

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

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

---

1.  아이디어

 

보드의 각 점을 8 x 8 체스판의 맨 왼쪽 맨 위 칸으로 하는 점이라고 가정하고 브루트포스 알고리즘을 적용해서 해결했다.

---

2. 문제풀이

 

보드에서 만들 수 있는 모든 체스판을 탐색했으며 검은색과 흰색이 번갈아 나오는 것은 행과 열 인덱스의 합이 짝수인지 홀수인지로 판단할 수 있었다. 각 점에 대해 색칠해야하는 개수를 구한 후 이들 중 가장 최솟값을 찾아 출력했다.

---

3. 코드

 

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[][] map = new char[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= N - 8; i++) {
            for (int j = 0; j <= M - 8; j++) {
                int cnt1 = 0;  // 맨 왼쪽 위 칸이 검은색인 체스판을 만드는 경우
                int cnt2 = 0;  // 맨 왼쪽 위 칸이 흰색인 체스판을 만드는 경우

                for (int a = i; a < i + 8; a++) {
                    for (int b = j; b < j + 8; b++) {
                        if ((a - i + b - j) % 2 == 0) {
                            if (map[a][b] == 'B') cnt2++;
                            else cnt1++;
                        } else {
                            if (map[a][b] == 'B') cnt1++;
                            else cnt2++;
                        }
                    }
                }

                min = Math.min(min, Math.min(cnt1, cnt2));
            }
        }

        System.out.println(min);
    }
}

---

4. 후기