백준 1018번 문제풀이 - 체스판 다시 칠하기

백준 1018번 문제풀이

 

 

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

1018번: 체스판 다시 칠하기

 

8 × 8 보다 같거나 큰 막 칠해진 체스판이 주어졌을 때 최소로 수정해서 체스판을 정상적으로 만드는 값을 출력하는

문제이다.

 

 

 

 

 

코딩

 

public class Chessboard {
    public static boolean[][] cb;
    public static int min = 64;
    // 수정횟수의 최솟값 구하는 메서드
    public static void findmin(int x, int y) {
        int row = x + 8;
        int col = y + 8;
        int count = 0;
        // 배열확인용
        boolean check = cb[x][y];
        for (int i = x; i < x + 8; i++) {
            for (int j = y; j < y + 8; j++) {
                if (check != cb[i][j]) { // 다른 색일 때 카운트
                    count++;
                }
                check = (!check); 
            }
            check = !check;
        }

        count = Math.min(count, 64 - count);
        min = Math.min(min, count);
    }

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

        cb = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            String chess = br.readLine();
            for (int j = 0; j < M; j++) {
                if (chess.charAt(j) == 'W') {
                    cb[i][j] = true;  // W일 때 true
                } else {
                    cb[i][j] = false; // B일 때 false
                }
            }
        }
        // 배열 크기에 따라 다른 경우의 수
        int N_row = N - 7;
        int M_col = M - 7;
        for (int i = 0; i < N-7; i++) {
            for (int j = 0; j < M-7; j++) {
                findmin(i, j);
            }
        }

        System.out.println(min);
    }
}

 

수정 횟수 최솟값을 구하는 메서드에서 check용 배열을 바꾸는 이유는 계속 색이 바뀌어야 되기 때문에 비교를 하고 카운트하기 위해서는 check용 배열을 바꾸어서 다시 카운트할 수 있게 했다. 그리고 줄이 바뀌면 위에 줄과 반대색으로 시작해야 되기 때문에 안의 for문이 끝나면 check용 배열을 바꾸게 된다.

 

count, 64 - count의 min을 구하는 이유는

둘 중 무엇이 최소인지 모르기 때문에 구하게 되는데

ex)

WWBWBWBW

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

                  이러한 경우 count는 63이 되기 때문에 W를 하나만 바꾸는 경우로 최소를 구하게 된다.

위의 알고리즘이 둘 중 뭐가 더 최소값인지 효율적인지를 판단하지 못하기 때문에 Math.min(count, 64 - count)로

판단하게 해야한다.

 

 

 

 

 

결과

 

 

 

 

 

 

 

느낀 점

 

머릿속으로 아이디어는 떠오르지만 코딩으로 알고리즘을 구현하는 데는 어려움이 많았다. 결국 온라인 선생님의 글을 보고 문제를 풀게 되었다. 알고리즘을 만들면서 생길 수 있는 예외사항을 생각해내는 것도 어려움이 많이 느껴져서 다양한 문제를 접해보고 반복학습을 해야겠다는 생각이 든다. 

 

 

 

 

 

참고 : https://st-lab.tistory.com/101

[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]