1018번-체스판 다시 칠하기

문제

---

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

 

준비물

---

cin.getline() - 체스판을 한줄씩 입력받기 위함.

담력 - 다중 for문을 두려워하지말기, 꼭 필요한 구문이라고 생각하기

코드

---

#include <iostream>

using namespace std;
 
char chessBoard[50][51];

int Search(char firstColor, int i, int j){
    int change = 0;
    char tileTemp;

    for(int iTemp = 0; iTemp < 8; iTemp++){
        for(int jTemp = 0; jTemp < 8; jTemp++){
            tileTemp =  chessBoard[i + iTemp][j + jTemp];

            if(jTemp % 2 == 0 && tileTemp != firstColor || 
               jTemp % 2 == 1 && tileTemp == firstColor) {
                change++;
            }
        }
    
        if(firstColor == 'B') firstColor = 'W';
        else firstColor = 'B';
    }

    return change;
}

int Solution(int N, int M){
    int change, MinChange = 64;

    cin.get();
    for(int i = 0; i < N; i++){
        cin.getline(chessBoard[i], 51);
    }

    for(int i = 0; i <= N - 8; i++){
        for(int j = 0; j <= M - 8; j++){
            change = Search('B', i, j);
            if(change < MinChange) MinChange = change;
            
            change = Search('W', i, j);
            if(change < MinChange) MinChange = change;
        }
    }

    return MinChange;
}

int main(){
    int N, M;

    cin >> N >> M;

    cout << Solution(N, M);

    return 0;
}

풀이

---

char[]의 특징과 배열 탐색을 할 줄 알면 누구나 가능한 쉬운 문제라 딱히 풀이가 없다

1. getline으로 체스판을 입력받는다.

2. 8*8로 탐색할 수 있는 모든 경우의 수를 탐색하면서, 고쳐야되는 체스칸의 수를 구한다 

2-1. 이외에 검정이 시작인 8*8, 하양이 시작인 8*8도 구해야 한다.

3. 지금까지 나온 고쳐야하는 체스칸의 수 중에 가장 적은 값을 구한다.

4. 출력. 

TML

---

cin.getline(char* s, streamsize n) 사용시 주의점

s - 저장할 문자열의 주소

n - 저장할 문자열의 최대 길이 => NULL값(문자열의 끝을 알리는 문자)도 별도로 포함해서 설정해줘야 한다 

 

char[] 사용시 주의점

NULL값(문자열의 끝을 알리는 문자)도 포함해야해서 원래 크기보다 1 더해줘야 한다  (되새김질)

 

이전에 개행문자(특히 엔터키)가 남아있을 것 같다면 cin비우기

cin을 초기화해주거나, cin.get()을 사용해서 getline이 개행문자까지 입력되는 것을 방지하자