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

 

실버 IV

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

1018번: 체스판 다시 칠하기

---

📌 문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

---

📤 입력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

---

📥 출력

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

---

💡 접근방법

체스판을 8X8만큼 검사한 방법은 N = 10, M = 10이라고 입력했을 경우

가로부터 옆으로 한 칸씩 이동하며 8X8만큼 검사를 하고, 가로를 다 검사를 했으면 한 칸 내려가 똑같이 가로부터 옆으로 한 칸씩 이동하며 8X8만큼 검사를 하였다.

검사 순서는 아래와 같다.

그 다음, check변수를 이용하여 chess[][]와 check가 다르면 색을 바꿔야 하는 걸로 판별하였다.

먼저, check의 초기값은 시작되는 색깔이 B라면 check = B, W라면 check = W로 시작되도록 하였다.

아래를 예시로 설명하자면 처음 시작이 chess[0][0] = W이므로 check의 초기값은 W가 된다.

그리고 그 옆인 chess[0][1]를 검사하기 전에 check가 W였으므로 B로 바꿔준다.

check는 B로 바꼈고, chess[0][1] = B이므로 둘이 같으므로 바꿀 필요가 없다. 

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

행이 바뀔 때는 맨 마지막으로 검사한 체스판과 시작되는 체스판이 같아야 한다. 

즉, chess[0][7] = B였으면 그 다음 행의 시작도 B여야 하므로, chess[1][0]도 B여야 한다.

행이 바뀌면 이전에 check를 변경했으므로 원래대로 되돌린다.

예를 들어, chess[0][7] = B였으면 check = W로 변경되었으므로, 그 다음 행의 시작인 check[1][0]는 check = B여야 하므로 행이 바꿔지면 다시 원래대로 check를 바꿔준다.

BWBBBWBW

 

위에서 chess[3][3]은 W여야 하는데 B가 왔다. 이때 check는 W로 되어 있을 것이다. check와 chess[3][3]의 값이 다르면 색을 바꿔줘야 한다는 것이므로 count1을 증가시킨다. 

이와 같은 방식으로 색을 바꿔야 하는 체스판의 개수를 세어주었다.

 

count2와 count1의 차이점은 시작되는 체스판의 색깔이 반대인 경우는 count2를 증가시켰다.

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

 

위의 예시로 설명하자면, chess[1][15] 부터 시작한 8X8만큼을 보면 check = B로 시작하게 되면 바꿔야 하는 개수가 32개가 된다. 하지만 check = W로 시작하게 되면 바꿔야 하는 개수가 31개가 된다. 

이와 같이 시작점이 다른 경우 바꿔지게 되는 체스판의 개수가 달라지는 것을 고려하여 count1과 count2로 나눠 세어주었다.

---

💻 코드

package Bruteforcing;

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

public class SLIVER4_BJ1018 {
    /*
        https://www.acmicpc.net/problem/1018
        체스판 다시 칠하기
     */
    static String [][] chess;
    static ArrayList<Integer> result = new ArrayList<>();
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        //N과 M입력
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        //체스판 입력
        String[] arr = new String[N];

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

        chess = new String[N][M];

        //한 줄로 된 문자열은 문자 하나씩 잘라 배열에 넣기
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++) {
                char charArr = arr[i].charAt(j);
                chess[i][j] = String.valueOf(charArr);
            }
        }

        for(int col = 0; col <= (N - 8); col++) {
            for(int row = 0; row <= (M - 8); row++) {
                find(col, row);
            }
        }

        //result배열 중에서 최솟값 출력
        System.out.println(Collections.min(result));

    }
    public static void find(int col, int row){

        int count1 = 0;
        int count2 = 0;
        
        //시작되는 chess가 W인 경우 check = W, 
        //B인 경우 check = B
        String check = chess[col][row];

        for (int i = col; i < col + 8; i++) {
            for (int j = row; j < row + 8; j++) {
                
                if(chess[i][j].equals(check)){
                    count2++;
                    
                    if(chess[i][j].equals("W")){
                        check = "B";
                    }
                    else{
                        check = "W";
                    }
                }
                else{
                    count1++;
                    if(chess[i][j].equals("W")){
                        check = "W";
                    }
                    else{
                        check = "B";
                    }
                }
            }
            if(check.equals("W")){
                check = "B";
            }
            else{
                check = "W";
            }
        }

        //result배열에 넣기
        result.add(count1);
        result.add(count2);
    }
}

---

📝 NOTE

ArrayList배열의 최솟값을 출력할 때는 Math.min()이 불가능하다. 따라서 Collections.min()을 사용해야 한다.

최대값도 마찬가지로 Collections.max()를 사용한다.

다른 분들의 코드를 보니 boolean을 이용하여 했는데 내가 생각보다 어렵게 생각한 것 같다.