[백준 알고리즘 C/C++] 1018번 문제 풀이: 체스판 다시 칠하기

** 이 글을 읽음에 앞서 포스팅 된 소스가 100% 정답은 아님을 밝힙니다.

    더욱 유능한 분께서 클린 / 최적의 소스를 짜셨을 가능성이 높습니다.

    기록용으로 남기며, 참고만 부탁드립니다.

** 백준 알고리즘은 직접 풀이를 해보시는 것을 권장합니다.

---

● 문제

난이도[티어] : 실버 4

백준 알고리즘 1018번 체스판 다시 칠하기

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

1018번: 체스판 다시 칠하기

 

---

● 풀이 방법

우선적으로 무식하게 검정색/하얀색 부터 시작하는 체스판을 선언해 놓았다. 

이후 입력받은 체스판이 될 판의 크기를 8x8로 나누어 색칠 해야 하는 경우의 수를 체크 후

가장 적은 숫자를 구하는 방식을 채용했다.

판에서 나올 수 있는 8x8의 모든 경우를 다 따져야하며 색칠하는 경우도 일일히 다 확인해야하기에

브루트포스 알고리즘(완전탐색) 기술을 사용하였다.

---

● 소스 코드

#include <iostream>

// 검정부터 시작하는 완벽한 체스판 경우
char B_start_board[8][8] = {
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'}
};

// 하양부터 시작하는 완벽한 체스판 경우
char W_start_board[8][8] = {
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'},
    {'W','B','W','B','W','B','W','B'},
    {'B','W','B','W','B','W','B','W'}
};

int main()
{
    int row, col;
    std::cin >> row >> col;
    char board[row][col];

    for(int i=0; i < row; i++){
        for(int j = 0; j < col; j++){
            std::cin >> board[i][j];
        }
    }
    int result = 64;
    //확인할 범위를 부분적으로 잘라 체스판을 다시 칠해야 하는 최소 수를 확인
    for(int y=0; y<row-7; y++){
        for(int x=0; x<col-7; x++){
            int start_W=0, start_B=0;
            for(int i=0; i<8; i++){
                for(int j=0; j<8; j++){
                    if(B_start_board[i][j] != board[y+i][x+j])
                        start_W++;
                    if(W_start_board[i][j] != board[y+i][x+j])
                        start_B++;
                }
            }
            if(result > start_W || result > start_B)
                result = start_W<start_B?start_W:start_B;
        }
    }
    std::cout << result;
}

 

판이 8x8이 되는 모든 경우의 수를 찾고 그 곳에서 하얀색 또는 검정색으로 칠했을 때의 최솟값을 계속해서 찾아내 구하는 완전탐색 방식으로 값을 도출했다.

 

---

● 결과

** 코드 길이가 상이 할 수 있습니다! 그러나 내용물은 같습니다.

    이유)  주석 및 더미 소스 유무