[BOJ] 1018 체스판 다시 칠하기

체스판 다시 칠하기

풀이

• M*N 크기의 보드. 검은색은 B, 흰색은 W로나타낸다.
• 이것을 잘라서 8*8로 나타내려고 한다.
• 검,흰이 번갈아서 칠해져 있어야 한다.
• 8*8로 잘라냈을 때, 몇 개의 정사각형을 다시 칠해야하는지, 최소 개수를 구해라.
• 8*8로 잘라야 하니까,세로 0~N-8 까지, 가로 M-8까지를 for문으로 돌리면서 시작점을 잡는다.
• 그 시작점부터 8*8 체스판 안을 보는데, 첫번째 줄이 BWBWBWBW 인 경우 랑 WBWBWBWB인 경우 두개가 있어서 이 둘의 경우를 다시 체크해야 하는 애들을 모두 체크한다. 그리고 나서 더 작은 수를 answer로 갱신한다.

정답 풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args)throws Exception {
        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];
        String[] stringMap = new String[N];
        for(int i=0;i<N;i++){
            stringMap[i] = br.readLine();
            map[i] = stringMap[i].toCharArray();
        }
        //8*8만큼 자르기
        int minVal = Integer.MAX_VALUE;
        for(int i=0;i<=N-8;i++){
            for(int j=0;j<=M-8;j++){
                int cnt = 0;
                for(int start=i;start<i+8;start++){
                        char[] temp;
                        if((start-i)%2==0){
                            temp = "BWBWBWBW".toCharArray();
                        }
                        else{
                            temp = "WBWBWBWB".toCharArray();
                        }
                        for(int startj=j;startj<j+8;startj++){
                            if(map[start][startj]!=temp[startj-j]){
                                cnt++;
                            }
                        }
                }
                minVal = Math.min(minVal,cnt);
                cnt = 0;
                    for(int start=i;start<i+8;start++){
                        char[] temp;
                        if((start-i)%2==0){
                            temp = "WBWBWBWB".toCharArray();
                        }
                        else{
                            temp = "BWBWBWBW".toCharArray();
                        }
                        for(int startj=j;startj<j+8;startj++){
                            if(map[start][startj]!=temp[startj-j]){
                                cnt++;
                            }
                        }
                    }
                minVal = Math.min(minVal,cnt);
            }
        }
        System.out.println(minVal);
    }
}

• 다른 풀이를 참고해보니까, 첫줄이 BWBWBWBW인 경우를 구십도 회전한게 WBWBWBWB이 된단다.
• 하나만 계산한 뒤, *2 해주면 답이 된다는 것.