[Algorithm] 99클럽 코테 스터디 11일차 TIL BOJ 1018

문제

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

풀이

문제 분석

• 완전탐색이라는 것을 알고 있었지만, 문제 이해에 어려움이 있었다
• 예를 들어서 다음과 같은 체스판이 있었다고한다면

WWWWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
WWWWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

• 이런 경우 첫번째에서 W를 시작으로할지 B를 시작으로 할지 결정하는 것에 따라 변경되는 개수가 달라질 수 있다는 점이었는데, 모든 칸을 수정하는 64개의 경우의 수에서 한가지 색으로 고정하여 센 값을 빼면 된다는 것을 떠올리지 못했다
• 또한 한줄씩 비교하는 개념은 똑같으나 BWBWBWBW, WBWBWBWB와 같이 문자열을 미리 고정해두고 줄 수의 나머지를 이용하여 비교할 생각은 또 하지 못했던 것 같다

코드

import java.io.*;
import java.util.*;

// 8*8 체스판을 만들 때

public class Main {
    static final char[] one = {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'};
    final static char[] two = {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int answer = 64;
        String line;
        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);

        char[][] board = new char[M][N];
        for(int i = 0; i<M ; i++) {
            line = br.readLine();
            for(int j= 0; j<N ; j++) {
                board[i][j] = line.charAt(j);
            }
        }

        for(int i = 0; i<=M-8 ; i++) {
            for(int j= 0; j<=N-8 ; j++) {
                answer = Math.min(answer, getCount(board, i, j));
            }
        }

        System.out.println(answer);

    }

    public static int getCount(char[][] board, int x, int y) {
        int blackCount = 0;
        int width = 0;
        int height = 0;
        for(int i = x; i<x+8 ; i++) {
            for(int j= y; j<y+8 ; j++, width++) {
                if(height%2 ==0) {
                    if(one[width] != board[i][j]) {
                        blackCount++;
                    }
                } else {
                    if(two[width] != board[i][j]) {
                        blackCount++;
                    }
                }
            }
            height++;
            width = 0;
        }
        return Math.min(blackCount, 64-blackCount);
    }
}

TIL

• 완전탐색이더라도 무언가 패턴을 찾거나 dp처럼 시간복잡도를 줄일 수 있는 수식이 존재함을 인지하고 이를 찾기 위해 노력해보아야겠다는 생각이 들었다
• 인덱스 관련해서 에러가 많이났었는데, 초기화 변수를 어느 위치에 두어야할지 잘 생각해야겠다