[백준] 1018번: 체스판 다시 칠하기 | C++ 풀이

# 문제

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

 

 

---

 

# 풀이

문제를 잘 읽자 100번 깜지 쓰겠습니다. 그냥 다시 색칠 보자마자 예전에 과제로 구현했던 코드 풀이랑 비슷할 것 같아 냅다 요상망측하게 구현하고 테스트 케이스 넣어보고 깨달았습니다. 8*8이라고요...

여러가지로 따져볼 게 있었던 브루트포스 문제다. 생각을 열심히 하면서 풀어보자.

바로 정답 소스코드부터 확인!

 

#include <iostream>
#include <algorithm>
using namespace std;

// 비교할 체스판 문양 2개를 미리 string 배열로 생성
string WB[8] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};
string BW[8] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
};

// 입력받은 m*n 보드를 받기 위한 배열
string board[50];

int cntWB(int x, int y);
int cntBW(int x, int y);

int main(){
    ios_base::sync_with_stdio(false);	// 두 표준 입출력 동기화 해제
    cin.tie(NULL);	// 입력과 출력 묶음을 풀기

    int n, m;
    cin >> n >> m;
    cin.ignore();

    for(int i=0; i<n; i++){
        getline(cin, board[i]);
    }
    int minVal = 65; // 8*8 칸 모두 다시 칠해도 64개
    
    for(int i=0; i+8 <= n; i++){
        for(int j=0; j+8 <= m; j++){
            int tmp = min(cntWB(i, j), cntBW(i, j));
            if(tmp < minVal) minVal = tmp;
        }
    }
    cout << minVal;
    return 0;
}

// W로 시작하는 체스판: 새로 칠해야 하는 칸 수 반환
int cntWB(int x, int y){
    int cnt = 0;
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            if(board[x+i][y+j] != WB[i][j]) cnt++;
        }
    }
    return cnt;
}

// B로 시작하는 체스판: 새로 칠해야 하는 칸 수 반환
int cntBW(int x, int y){
    int cnt = 0;
    for(int i=0; i<8; i++){
        for(int j=0; j<8; j++){
            if(board[x+i][y+j] != BW[i][j]) cnt++;
        }
    }
    return cnt;
}

우선 main 함수에 들어가기 앞서 해줄 것이 두 가지 있다.

 

1. 비교할 체스판 배열과 board 배열 만들기

: 체스판은 문제에서 언급한대로 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 두 가지가 있다.

따라서 W로 시작하는 8*8 배열을 WB 배열, B로 시작하는 8*8 배열을 BW 배열로 미리 만들어주었다.

: 입력받는 m*n 보드는 최대 50*50의 크기를 가지고 있다. 따라서 비교할 체스판 배열과 같이 string 1차원 배열로 만들되, 크기를 50으로 주어 50*50의 m*n 보드가 모두 담기도록 하였다. 전역변수로 구현해준 이유는 2번에서 만들 함수에서도 접근이 가능하도록 만들기 위해서다.

 

2. 새로 칠해야 할 칸의 수를 구하는 함수 구현

: 함수를 구현하기에 앞서 주의할 것이 있는데 8*8칸으로 자른 맨 왼쪽 위 칸이 W이든 B든, W로 시작하는 경우와 B로 시작하는 경우 두 가지를 모두 고려해 새로 칠해야 할 칸의 수를 구해야 한다는 것이다. 무슨 말이냐면, 8*8의 맨 왼쪽 위 칸이 W여도 이 칸부터 B로 새로 칠하는 경우가 최솟값일 수 있는 것! W로 시작한다고 WB 배열과 비교하는 게 무조건 최솟값이 아니라는 거지... 사실 제가 이걸 놓쳤어요

: 따라서 두 가지를 모두 구현해 새로 칠할 칸의 수를 반환하는 int cntWB(int x, int y), int cntBW(int x, int y) 함수를 구현했다. 해당 함수들은 board에 입력받은 보드를 8*8로 잘라가며 미리 만들어둔 WB, BW 체스판과 비교해준다. 8*8로 자르는 위치를 계속해서 옮겨줘야 하기 때문에 인덱스에 주의하자. 그리고 새로 칠해야 할 경우는 카운트하여 최종 값을 반환!

 

 

 

int n, m;
cin >> n >> m;
cin.ignore();

for(int i=0; i<n; i++){
    getline(cin, board[i]);
}

main 함수에서는 n과 m을 선언 후 입력을 받아오고, 보드판을 한줄씩 받아 미리 생성해둔 board 배열에 넣어주면 된다.

이때 getline을 사용하기 때문에 개행문자가 읽히지 않도록 n과 m이 입력된 후 버퍼를 한 번 비워준다.

 

 

 

int minVal = 65; // 8*8 칸 모두 다시 칠해도 64개
    
    for(int i=0; i+8 <= n; i++){
        for(int j=0; j+8 <= m; j++){
            int tmp = min(cntWB(i, j), cntBW(i, j));
            if(tmp < minVal) minVal = tmp;
        }
    }
    cout << minVal;

새로 칠해야 하는 정사각형의 수는 8*8 모두 다시 칠한다고 해도 (격자무늬라 사실 이럴 일은 없다) 64칸이므로 넉넉히 65로 선언 및 초기화를 해두고, for문을 돌며 다시 칠해야 하는 칸의 최솟값을 구해준다. 이때 for문에서는 8*8칸을 잘라가며 구현하니 조건식 범위 지정에 신경써야 한다.

algorithm 헤더에 정의된 min 함수를 통해 WB배열과 비교해 다시 칠해야 하는 칸 수, BW배열과 비교해 다시 칠해야 하는 칸 수 중 더 작은 값을 tmp라는 임시 변수에 저장한다. 그리고 만약 이 값이 미리 정의해둔 minVal 값보다 작다면 minVal을 tmp값으로 대체하고 다음 8*8 보드 탐색! 

이중 for문을 통해 모든 8*8 경우를 따져본 후 마지막으로 남아있는 minVal을 출력해주면 끝이다.

 

이상하게 삽질 여러번 한 코드... 벌써 이러면 안되는데!

 

 

 

 

 

---

 

 

 

1018번: 체스판 다시 칠하기