[Baekjoon] 1018 - 체스판 다시 칠하기

📝 문제

 

 

❗ 주의

자른 보드판의 시작이 W라고해서 무조건 W로 시작하게 색칠해야 하는것이 아니다.

① WBWBWB... 로 칠하거나

② BWBWBW... 로 칠해야 하는 

총 두가지 경우 중 가장 적게 칠해야 하는 경우를 구해야 하는것이 포인트.

 

 

 

🔑 풀이 과정

나는 정말 단순하게 풀었다.

① 크기가 8 x 8인 맨 왼쪽 위 칸이 W인 체스판, 맨 왼쪽 위 칸이 B인 체스판 총 2가지를 2차원 배열로 미리 작성해둔다.

② N행 M열인 보드판을 2차원 배열로 입력받는다.

③ 해당 보드판을 8 x 8 크기로 자르는 경우는 총 (N-7) * (M-7) 가지 경우가 존재한다. 

→ 입력받은 보드판 배열을 board라 할 때,

맨 왼쪽 위 칸의 인덱스가

board[0][0] ~ board[0][M-8]

...

board[N-8][0] ~ board[N-8][M-8] 인 경우들

④ 각 자를 수 있는 경우마다

맨 왼쪽 위 칸이 W인 체스판으로 만들 때 색칠해야 하는 값,

맨 왼쪽 위 칸이 B인 체스판으로 만들 때 색칠해야 하는 값

(1번에서 작성했던 배열과, 자른 보드판의 값을 비교하여 값이 다를때 count를 증가시키면 된다.)

그 두 가지를 구해서 더 작은 값을 구한다.

⑤ 그 작은 값을 모든 경우마다 비교해서 제일 작은 값을 구한다.

 

 

 

* 참고 이미지

N = 10, M = 13인 보드판을 

8 * 8크기로 자르는 경우

(핑크색으로 색칠한 부분 = 자를 수 있는 경우들의 맨 왼쪽 위칸)

 

 

 

🔓 답안

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

public class Main {

    static char[][] ans1 = {
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
    };

    static char[][] ans2 = {
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
            {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
            {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
    };

    static char[][] b;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); //N개의 줄
        int M = Integer.parseInt(st.nextToken());

        //보드판 입력받기
        b = new char[N][M];
        for(int i = 0; i < N; i++){
            String str = br.readLine();
            for(int j = 0; j < M; j++){
                b[i][j] = str.charAt(j);
            }
        }

        //체스판이 8*8 이므로, 가장 많이 틀렸을때의 값이 64
        int min = 64;
        for(int i = 0; i < N-7; i++){
            for(int j = 0; j < M-7; j++){
                int s = check_w(i, j);
                int t = check_b(i, j);

                int z;
                if(s < t)
                    z = s;
                else
                    z = t;

                if(z < min)
                    min = z;
            }
        }

        bw.write(min + "\n");
        bw.flush();
        bw.close();

    }

    static int check_w(int i, int j){
        int count = 0;

        for(int r = 0; r < 8; r++){
            for(int c = 0; c < 8; c++){
                if(ans1[r][c] != b[r+i][c+j])
                    count++;
            }
        }

        return count;
    }

    static int check_b(int i, int j){
        int count = 0;

        for(int r = 0; r < 8; r++){
            for(int c = 0; c < 8; c++){
                if(ans2[r][c] != b[r+i][c+j])
                    count++;
            }
        }

        return count;
    }

}

 

🖤 알고리즘 분류

- 브루트포스 알고리즘