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

 

1018번: 체스판 다시 칠하기

 

 

 

문제 

1x1 정사각형 구획으로 나뉘어져 있는 MxN 크기의 보드에 한 구획마다 흰색 또는 검은색이 무작위로 칠해져 있을 때, 인접하는 구획끼리 서로 다른 색을 갖도록 하여 8x8 크기의 체스판을 만들기 위해 다시 칠해야 하는 정사각형 구획의 최소 개수를 구하여라.

 

 

 

 

 

조건

만들고자 하는 체스판의 크기는 8 x 8

8 <= N, M

시간제한 2초

 

 

 

풀이방향

입력으로 주어지는 보드의 크기 N, M이 비교적 작기 때문에 완전 탐색(브루트 포스)으로 해결 가능하다.

풀이 방향을 생각해보면 문제에 힌트가 있다. 체스판을 색칠하는 경우는 두 가지뿐이며, 하나는 맨 왼쪽 위 칸이 흰색인 경우이고 다른 하나는 맨 왼쪽 위 칸이 검은색인 경우이다. 따라서 전체 MxN보드 중에서 8x8 사이즈의 부분에 대해서 맨 왼쪽 위 칸이 흰 색인 경우와 검은색인 경우 칠해야 하는 횟수를 구하면서 최소값을 최신화 시켜준다. 보드를 저장하는 배열 타입은 검은색 or 흰색이므로 true or false 데이터만 저장하는 boolean 을 사용해도 된다. 

 

8x8 사이즈의 보드 일부분에 대해서 맨 왼쪽 위 칸이 흰색인 경우와 검은색인 경우에 대하여 칠해야 하는 횟수를 구한다. 우선 맨위 왼쪽 구획의 색깔을 시작 색(start)으로 정한다. 그 다음 이중 배열을 사용하여 1열씩 바꾸어 칠하는 횟수를 계산한다.

핵심은 가로로 이전 색과 비교하여 색이 같다면 색을 바꾸어 칠하는 것이다. 따라서 원래 칠해져 있어야 하는 색에 대한 정보를 담은 변수가 color라고 할 때 color가 실제로 칠해져 있는 색과 다르면 count++해준다. 그 다음 오른쪽 칸에는 현재 색과 반대되는 색이 들어가야 하므로 color을 뒤집어준다. 

 

세로로 인접한 구획들도 마찬가지로 서로 다른 색이어야 하므로, 하나의 행에 대한 탐색이 끝나고 다음 행에 대한 탐색을 시작하기 전에 color를 뒤집어준다.

 

 

int count = 0;
boolean start = board[r_start][c_start];

for (int i = r_start; i < r_end; i++) {

    boolean color = start;

    for (int j = c_start; j < c_end; j++) {

        if (board[i][j] != color) count++;

        color = !color;
    }

    start = !start;
}

 

 

그림으로 간단하게 설명하자면

 

 

 

 

 

 

예제 입력 2의 보드이다.

현재 8x8 체스판 구역의 맨 위 왼쪽 칸의 색은 검은색(color = B)이다. 따라서 start와 color(현재 색)는 true(true = 검은색 이라고 임의로 정함)이다. 1행 1열의 색은 검은색으로 현재 색이어야 하는 color와 동일하다. 따라서 color만 반전시키고 탐색을 이어간다. 그 다음 1행 2열의 색을 보니 color정보에 의하면 흰색이어야 하는데 board에 칠해져 있는 색은 검은색이다. 이 경우 색을 바꾸어 칠해야 하므로 count를 1 더해주고 color을 반전시켜준다. 1행 3열의 경우 color 정보는 검은색이고 실제로 칠해진 색도 검은색이므로 color만 반전시킨다. 

그리고 1행에 대한 탐색이 끝나고 2행에 대한 탐색이 시작되기 전에 시작색인 start을 반전시켜준다. 

 

 

 

 

 

처음 풀었을 때에는 맨 왼쪽 색상이 흰색일 때와 검은색일 때 두 가지 경우에 대하여 위 과정을 반복하였는데, 다른 사람의 풀이를 참고해보니 문제 특성상 굳이 두 경우 모두 계산하지 않아도 된다는 것을 알았다.

체스판은 흰색 또는 검은색 두 색상이 교차한다. 만약 맨 위 왼쪽 칸이 흰색인 경우를 case1, 맨 위 왼쪽 칸이 검은색인 경우를 case2라고 할 때, case1 모양을 만들면서 칠하지 않은 부분들은 case2 모양을 만들기 위해서는 칠해야 하고 동시에 case1 모양을 만들면서 바꾸어 칠한 부분은 case2 모양을 만들기 위해서는 바꾸어 칠하지 않아도 된다. boolean 처럼 검은색 또는 흰색 둘 중 하나이기 때문에 가능하다.

따라서 case2의 count는 전체 체스판 크기에서 case1의 count를 빼준 값과 동일하다.

 

 

 

 

 

 

 

전체 코드

import java.io.*;

public class Main {
    
    static final char black = 'B';
    static final char white = 'W';
    static final int size = 8;
    
    static boolean[][] board;
    static int N, M;
    
    public static void main (String[] args) throws IOException {
        
// 입력 시작
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        
        
        board = new boolean[N][M];
        
        
        for (int i = 0; i < N; i++) {
            
            String row = br.readLine();
            
            for (int j=0; j<M; j++) {
                
                if (row.charAt(j) == black) 
                    board[i][j] = true;
                
                else
                    board[i][j] = false;
            }
        }
// 입력 끝        
        
        int min = Integer.MAX_VALUE;
        
        // 주어진 보드에 대한 완전 탐색
        for (int i = 0; i + size <= N; i++) {
            
            for (int j = 0; j + size <= M; j++) 
                
                // 칠해야 하는 횟수의 최소값 최신화
                min = Math.min(min, countColorChange (i, j));
        }
        
        
        System.out.println(min);
        
        br.close();
    }
    
    static int countColorChange (int r_start, int c_start) {
        
        int r_end = r_start + size;
        int c_end = c_start + size;
        
        
        int count = 0;
        boolean start = board[r_start][c_start];
        
        for (int i = r_start; i < r_end; i++) {
            
            // i행의 맨 왼쪽 시작 색
            boolean color = start;
            
            for (int j = c_start; j < c_end; j++) {
                
                // 칠해져 있어야 하는 색상이 아닌 다른 색이 칠해져 있으면 바꾸어 칠해야 한다.
                if (board[i][j] != color) count++;
                    
                color = !color;
            }
            
            // 다음 행의 맨 왼쪽 시작 색
            start = !start;
        }
        
        
        count = Math.min(count, (size * size) - count);
        
        
        return count;
    }
}