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

1) 생각

N x M의 크기의 체스판을 만들 판이 주어진다 판들은 1x1의 크기로 W(흰색)과 B(검은색)으로만 이루어져있다.

판에서 8 x 8을 떼어내어 체스판을 만들 때, 최소한으로 바꿔야하는 W와 B의 개수를 구하여라.

처음 생각

8 x 8을 분리하여 그 판의 왼쪽 맨 위에서부터 다음 판과 색이 같은지 판단하여 다르다면 임시변수 temp에 다음 판의 색을 저장하고 있고,

색이 같다면 카운트 변수를 +1 시켜준 후 temp의 색을 바꿔준다.(BBB 일경우 temp의 색을 바꿔주지 않으면 앞 뒤로 중복 카운트가 된다.)

▶시뮬레이션 유형의 문제는 일단 문제가 길기 때문에 문제를 제대로 보지 못할 아니 않을 가능성이 크다. 이 문제의 경우에는 문제속에 힌트를 많이 주고 있다.

▶문제의 마지막에 큰 힌트가 주어져있다. "왼쪽 위의 시작이 B일 때와 W일 때 두가지가 나타날 수 있다."

▶처음 작성했던 것은 맨 처음의 색을 얻어서 그 색을 기준으로 다음 색과 쭉 판단해 나갔기에 제출시 '틀렸습니다'가 나오게 되었다.(일부로 만드신건지는 모르겠지만 예제로 주어진 케이스는 이렇게 해도 통과가 된다.)

다음 생각

맨 처음 시작이 B일 때와 W일 때, 2가지의 탐색을 진행한다.

2) 방안

1) 배열을 바꿔가며 진행하면 메모리와 시간을 크게 잡아 먹기 때문에 temp 변수로 색만 비교하면서 진행하였다.

▶W를 C로 적어놓는 바람에 왜 틀렸는지 찾는데 시간이 조금 걸렸다. 역시 사람은 무의식에 잘 사로잡히는것 같다. B 다음은 C라고 생각했던것 같다.

2) 흰색과 검은색을 각각 탐색해도 되겠지만 solve() 메소드에 모아놓았으므로 result 변수를 두개 사용하여 둘을 분리하였다.

3) 최소값만 알면 되므로 전체 result를 Field 영역에 선언하여 탐색중 해당 result 값을 넘어갔을 경우 바로 탐색을 중지하면 속도가 더 빠를것이다.

▶실제로 바꿔보니 그렇게 개선되지는 않았다. 테스트 케이스가 평균적으로 잘 잡혀 있는것 같다.

import java.util.Scanner;
 
public class Main {
    static int n,m;
    static int[][] arr;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 행
        m = sc.nextInt(); // 열
        arr = new int[n][m];
        for(int i=0;i<n;i++) {
            String t = sc.next();
            for(int j=0;j<m;j++)
                arr[i][j] = t.charAt(j);
        }
        // 8 * 8 을 살펴보자
        int result = Integer.MAX_VALUE;
        for(int i=0;i<=n-8;i++) {
            for(int j=0;j<=m-8;j++) {
                result = Math.min(result, solve(i,j));
            }
        }
        System.out.println(result);
    }
    
    private static int solve(int x,int y) {
        // 하나는 시작이 검은색 , 하나는 시작이 흰색
        // 검은색이 B 흰색이 W이다... C로 했었다.
        // 1. 시작이 검은색
        int result = 0;
        int temp = 'B';
        for(int i=x;i<x+8;i++) {
            // 줄의 시작은 이전과 같아야 한다.
            if(arr[i][y]!=temp) result++;
            for(int j=y+1;j<y+8;j++) {
                if(arr[i][j]==temp) {
                    result++;
                    // +1을 해주었으니 바꿔준다.
                    // (BBB 일경우 앞에 2개 비교후 중복 카운트를 막기 위해)
                    if(temp=='B') temp = 'W';
                    else temp = 'B';
                }else temp = arr[i][j];
            }
        }        
        // 2. 시작이 흰색
        int result2 = 0;
        temp = 'W';
        for(int i=x;i<x+8;i++) {
            if(arr[i][y]!=temp) result2++;
            for(int j=y+1;j<y+8;j++) {
                if(arr[i][j]==temp) {
                    result2++;
                    if(temp=='B') temp = 'W';
                    else temp = 'B';
                }else temp = arr[i][j];
            }
        }
        
        return result>result2?result2:result;
    }
}