백준 - 1018 - 체스판 다시 칠하기

---

풀이 과정

흰색 또는 검은색으로 칠해진 N × M 칸을 이룬 판에서 정해지지 않은 위치에서 8 × 8 의 사각형으로 잘라서 체스판을 만든다.

그 후 공유하는 변이 겹치지 않게 색을 칠하는데 가장 적은 칸을 칠해야하는 최솟값을 구하는 문제이다.

사각형을 한 칸씩 움직이면서 하나하나 칸을 비교하면서 문제를 풀어야 한다.

 

2가지 방법

: 보드판을 char 와 boolean 으로 받는 방법을 이용했다.

 

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

public class B_1018_2 {

    private static final char[][] WHITE = {
            {'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'},
    };

    private static final char[][] BLACK = {
            {'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'},
    };

    private static char[][] board;

    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());

        board = new char[N][M];

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


        int result = Integer.MAX_VALUE;

        for(int i = 0; i < N - 7; i++){
            for(int j = 0; j < M - 7; j++){
                int count = solve(i, j);
                if(result > count){
                    result = count;
                }
            }
        }
        System.out.println(result);
    }

    private static int solve(int x, int y){

        int white = 0;
        int black = 0;

        for(int i = x; i < x + 8; i++){
            for(int j = y; j < y + 8; j++){
                if(board[i][j] != WHITE[i - x][j - y]){
                    white++;
                }
                if(board[i][j] != BLACK[i - x][j - y]){
                    black++;
                }
            }
        }
        return Math.min(white, black);
    }
}

 

 

 

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

public class B_1018 {

	// 하얀색으로 시작하는 보드판
    private static final boolean[][] WHITE = {
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
    };
    
	// 검정색으로 시작하는 보드판
    private static final boolean[][] BLACK = {
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
            {false, true, false, true, false, true, false, true},
            {true, false, true, false, true, false, true, false},
    };

    private static boolean[][] board;

    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());
		
       board = new boolean[N][M];

        for(int i = 0; i < N; i++){
            String[] line = br.readLine().split("");

            for(int j = 0; j < M; j++){
                board[i][j] = line[j].equals("W");
            }
        }

        int result = Integer.MAX_VALUE;

        for(int i = 0; i < N - 7; i++){
            for(int j = 0; j < M - 7; j++){
                int count = solve(i, j);
                if(result > count){
                    result = count;
                }
            }
        }
        System.out.println(result);
    }

    private static int solve(int x, int y){

        int white = 0;
        int black = 0;

        for(int i = x; i < x + 8; i++){
            for(int j = y; j < y + 8; j++){
                if(board[i][j] != WHITE[i - x][j - y]){
                    white++;
                }
                if(board[i][j] != BLACK[i - x][j - y]){
                    black++;
                }
            }
        }
        return Math.min(white, black);
    }
}

 

 

 

참고 블로그 : https://blog.itcode.dev/posts/2021/06/26/a1018