알고리즘/BOJ

백준 1018번 체스판 다시 칠하기

꾸준함. 2018. 7. 6. 15:50

문제 링크입니다: https://www.acmicpc.net/problem/1018


체스판은 (0,0)에 W가 오는 경우가 있고 B가 오는 경우가 있습니다.

따라서 두 가지 경우의 체스판을 미리 선언해놓고 하나하나 Brute Force 방식으로 비교하면 쉽게 풀 수 있는 문제였습니다.

비교하는 범위가 초과하지 않도록만 한다면 딱히 주의할 점은 없는 것 같습니다!


#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 50;

 

int M, N;

string board[MAX];

//(0, 0) W인 체스보드

string whiteFirst[8] = {

        { "WBWBWBWB" },

        { "BWBWBWBW" },

        { "WBWBWBWB" },

        { "BWBWBWBW" },

        { "WBWBWBWB" },

        { "BWBWBWBW" },

        { "WBWBWBWB" },

        { "BWBWBWBW" }

};

//(0, 0) B인 체스보드

string blackFirst[8] = {

        { "BWBWBWBW" },

        { "WBWBWBWB" },

        { "BWBWBWBW" },

        { "WBWBWBWB" },

        { "BWBWBWBW" },

        { "WBWBWBWB" },

        { "BWBWBWBW" },

        { "WBWBWBWB" }

};

 

//(0, 0) W인 체스보드 기준 바뀔 칸 수

int whiteFirstChange(int y, int x)

{

        int cnt = 0;

        for (int i = y; i < y + 8; i++)

                 for (int j = x; j < x + 8; j++)

                         if (board[i][j] != whiteFirst[i - y][j - x])

                                 cnt++;

 

        return cnt;

}

 

//(0, 0) B인 체스보드 기준 바뀔 칸 수

int blackFirstChange(int y, int x)

{

        int cnt = 0;

        for (int i = y; i < y + 8; i++)

                 for (int j = x; j < x + 8; j++)

                         if (board[i][j] != blackFirst[i - y][j - x])

                                 cnt++;

 

        return cnt;

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

                 cin >> board[i];

 

        int result = INF;

 

        for (int i = 0; i + 7 < N; i++)

                 for (int j = 0; j + 7 < M; j++)

                         result = min(result, min(whiteFirstChange(i, j), blackFirstChange(i, j)));

 

        cout << result << endl;

        return 0;

}


개발환경:Visual Studio 2017


지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 10798번 세로읽기  (0) 2018.07.07
백준 1924년 2007년  (0) 2018.07.06
백준 1720번 타일 코드  (2) 2018.07.06
백준 1695번 팰린드롬 만들기  (2) 2018.07.06
백준 2580번 스도쿠  (9) 2018.07.05