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

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

이번 문제도 브루트 포스 알고리즘을 사용하여 해결하면 된다.

N * M 크기의 체스판이 주어지는데, 1, 1(첫 줄, 첫 번째)번 칸부터 8 * 8 크기의 칸을 모두 확인하여 해당 범위 내에 몇 개의

사각형을 다시 칠해야 하는지 구한다.

이를 1, 1 칸부터 N - 7, M - 7 번 칸까지 반복하며 확인하자.

확인을 위해 1, 1 칸이 검정색으로 시작하는 8 * 8 크기의 보드 배열, 흰색으로 시작하는 보드 배열을 만들고

각 칸이 같은지 비교한다.

모두 비교하여 가장 적은 수의 사각형을 칠해야 하는 경우를 출력하자.

 

 

 

3. 문제 풀이

 

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

int main() {
    int n, m, repaint = 250;
    string b_board[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB" };
    string w_board[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW" };
    string board[50];

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

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

    for (int i = 0; i < n - 7; i++) {
        for (int j = 0; j < m - 7; j++) {
            int check1 = 0, check2 = 0;
            for (int k = 0; k < 8; k++) {
                for (int y = 0; y < 8; y++) {
                    if (board[i + k][j + y] != b_board[k][y]) check1++;
                    if (board[i + k][j + y] != w_board[k][y]) check2++;
                }
            }
            if (repaint >= check1) repaint = check1;
            if (repaint >= check2) repaint = check2;
        }
    }
    cout << repaint;
}

 

정수형 변수 n, m, repaint(최소 색칠 개수 저장 변수) 를 선언, repaint 를 250으로 초기화.

첫 블록이 검정색일때의 보드인 문자열 배열 b_board 와 첫 블록이 흰색일때의 보드인 문자열 배열 w_board 를 생성.

크기가 50인 문자열 배열 board 를 선언.

 

cin 으로 입력받을 보드의 크기 N 과 M 을 입력받아 각각 n 과 m 에 저장한다.

아래 보드의 상태 입력 부분에서 getline 함수를 사용할 것이기 때문에 멤버함수 ignore() 로 입력 버퍼를 비워준다.

 

for문을 사용하여 getline 으로 board 문자열 배열에 n 줄의 문자열을 입력받아 저장한다.

이것으로 현재 보드 상태를 입력받는다.

 

2중 for문을 사용하여 보드의 0, 0 번 칸부터(1, 1 이지만 배열이므로 0, 0 번 인덱스로 참조) N - 7, M - 7 번 칸까지 순회한다.

첫 블록이 검정, 흰색일 때의 블록 색칠 갯수를 카운트 할 변수 check1, check2 를 선언한다.

다시 2중 for문으로 해당 위치부터 8 * 8 크기의 배열을 순회하며 각 값이 b_board, w_board 의 각 값과 다른지 비교한다.

값이 다른 경우 각 변수에 1을 더한다.

두 번째 2중 for문이 끝나면 if문으로 repaint 변수의 값과 check1, 2 변수의 값을 비교하여 작은 값을 repaint 에 저장한다.

이것으로 색칠 횟수가 적은 경우를 repaint 변수에 저장한다.

 

모든 반복문이 끝나면 cout 으로 repaint 를 출력하여 최소 색칠 횟수를 출력한다. 

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

.