백준 - 체스판 다시 칠하기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1018

[문제 설명]

M*N 크기의 보드판이 주어졌을 때, 8*8로 잘라서 체스판을 만드려고 한다.

체스판을 칠한 횟수가 가장 적은 경우를 구하여라.

 

[접근 방법]

기초적인 완전탐색 문제인데, 굉장히 오랜 시간이 걸려서 풀었다. 

이유는 변수의 명을 나름대로 뜻 있게 줬는데 행과 열 부분은 i,j와 같이 단순히 줘서 헷갈렸다.

이로 인해 많은 시간을 뺏겼다.

 

접근 방법은

예를 들어, BBBBW일 경우 B로 시작하면 BWBWB로 3번 덧칠해야한다.

반면에 W로 시작하면 WBWBW 2번 덧칠해야한다.

 

나는 이걸 통해 (보드의 크기) = (B로 칠한 경우) + (W로 칠한 경우)라고 생각했고

(B로 칠한 경우) = (보드의 크기) - (W로 칠한 경우)

(W로 칠한 경우) = (보드의 크기) - (B로 칠한 경우)라고 생각했다.

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

class Main {
    static char[][] board;
    static int N;
    static int M;
    static int sizeOfChessBoard = 8*8;
    public static void main(String[] args) throws IOException {
        // 입력 받기
        int answer = Integer.MAX_VALUE;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        N = Integer.parseInt(firstLine[0]);
        M = Integer.parseInt(firstLine[1]);
        board = new char[N][M];
        for (int i = 0; i < N; i++) {
            board[i] = br.readLine().toCharArray();
        }

        // 타일을 한칸씩 이동하면서 8*8 체스판 만들기
        for (int row = 0; row <= N-8; row++) {
            for (int col = 0; col <= M-8; col++) {
                answer = Math.min(countBoard(col,row), answer);
            }
        }

        System.out.println(answer);
    }

    // 색칠해야 되는 개수를 구하는 메소드
    private static int countBoard(int col, int r) {
        // 이번 줄의 시작 색깔
        char pivot = 'B';
        // 이전 줄의 시작 색깔
        char prevPivot = pivot;
        // 색칠해야 하는 판의 수의 총합
        int countOfHasToColor = 0;

        // 보드 전체를 조회해서 색칠해야 하는 판의 수를 구함
        for (int row = r; row <= r+7; row++) {
            for (int column = col; column <= col+7; column +=1) {
                // 색칠해야 하는 색과 다르면 덧칠해야함.
                if (board[row][column] != pivot) {
                    countOfHasToColor++;
                }
                // 다음 칸은 다른 색으로 넘어가야하므로 색 변경
                pivot = (pivot=='B') ? 'W' : 'B';
            }
            // 다음 줄은 이전 줄에 색깔에 반대 색으로 시작
            pivot = (prevPivot == 'B') ? 'W' : 'B';
            // 이전 줄에 기준을 최신화
            prevPivot = (prevPivot == 'B') ? 'W' : 'B';
        }

        // B로 시작하는 경우의 수는 countOfHasToColor, W로 시작하는 경우의 수는 sizeOfChessBoard-countOfHasToColor
        // 최솟값을 구하므로 둘 중의 작은 수를 리턴.
        return Math.min(countOfHasToColor,sizeOfChessBoard-countOfHasToColor);
    }
}

[시간복잡도와 공간복잡도]

시간복잡도는 보드판을 8*8로 자를 수 있는 경우의 수가 (N-7)*(M-7)이고

만들어진 보드를 매번 전부 검색해야 하므로 8*8을 곱해야 한다.

따라서 (N-7)(M-7)*8*8이 되는데, 시간복잡도는 최고차항만 취급하므로 O(NM)이 시간 복잡도가 된다.

공간복잡도도 주어진 보드판을 재현하는데 사용된 NM이 된다