본문 바로가기
알고리즘

[백준 1018] 알고리즘 34일차 : 체스판 다시 칠하기

by SiO2whocode 2020. 7. 30.
반응형

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

 

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

브루트포스 C++
규칙없이 칠해져있는 큰 판을 잘라서 8*8체스판을 만드는데 다시 칠해야 하는 칸이 최소인 경우 최솟값을 출력하는 문제

예전에 입력값 긴거 보고 패스했었는데 실버5라고 떠서 브루트포스 끝낼겸 시도해봤다.
접근방법
우선 접근방법은 브루트포스인 만큼 입력받은 큰 판에서 8*8판이 만들어 지는 모든 경우를 조사하는 것이다.
체스판을 다시 칠하는 칸의 개수를 조사하는 과정은
처음엔 토글하면서 다시 칠해야하는 칸의 개수를 세어 보려고 했다. 근데 어차피 8*8인 체스판을 만드는 경우의 수는 두가지 경우 뿐이라 완성된 8*8체스판 두개로 판 찍듯이 검사해도 됐다.
그래서 흰색으로 시작하는 8*8체스판과 검은색으로 시작하는 8*8체스판을 미리 배열에 담아놨다. 그리고 나서 일치하지 않는 경우 카운트해서 최솟값을 출력했다.

첫번째 칸을 다시 칠하는 경우를 고려하지 않아서 틀렸었고 모든 경우에대해 흰색으로 시작하는 판과 검은색으로 시작하는 판을 모두 검사하도록 고쳐서 통과됐다.

소스코드
(이따 올릴게유 폰이라 안올라감)

#include <iostream>
using namespace std;
char board[51][51];
char startByW[9][9] = {
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
};
char startByB[9][9] = {
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
};
int getStartByW(int sr, int sc){
    int cnt = 0;
    for(int r = sr, rr = 0; rr < 8; r++, rr++){
        for(int c = sc, cc = 0; cc < 8 ; c++, cc++){
            if(board[r][c] != startByW[rr][cc]){
                cnt++;
            }
        }
    }
    return cnt;
}
int getStartByB(int sr, int sc){
    int cnt = 0;
    for(int r = sr, rr = 0; rr < 8 ; r++, rr++){
        for(int c = sc, cc = 0; cc < 8 ; c++, cc++){
            if(board[r][c] != startByB[rr][cc]){
                cnt++;
            }
        }
    }
    return cnt;
}
int getResult(int sr, int sc){
    return min(getStartByB(sr, sc), getStartByW(sr, sc));
}
int main(){
    int row, col;
    cin >> row >> col;
    
    for(int r = 0 ; r < row ; r++){
        cin >> board[r];
    }
    int min = 65;
    int semiResult;
    for(int r = 0 ; r <= row-8 ; r++){
        for(int c = 0 ; c <= col-8 ; c++){
            semiResult = getResult(r,c);
            if(min >= semiResult)
                min = semiResult;
        }
    }
    cout << min;
    
    return 0;
}
반응형

댓글0