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

문제 출처: www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

1. 코드

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

const char b[8][9] = {
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"}
};
const char w[8][9] = {
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"}
};

int black(int x, int y);
int white(int x, int y);
char board[50][50];

int main()
{
    int row, columns, result = 123456;
    cin >> row >> columns;

    for (int i = 0; i < row; i++)
        cin >> board[i];

    for (int i = 0; i < row - 7; i++)
    {
        for (int j = 0; j < columns - 7; j++)
        {
            result = min(result, min(white(i, j), black(i, j)));
        }
    }
    cout << result << endl;
    return 0;
}

int black(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] != b[i][j])
                cnt++;
        }
    }
    return cnt;
}

int white(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] != w[i][j])
                cnt++;
        }
    }
    return cnt;
}

(실행)

2. 풀이

const char b[8][9] = {
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"}
};
const char w[8][9] = {
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"},
    {"WBWBWBWB"},
    {"BWBWBWBW"}
};

먼저 비교를 편하게 하기 위하여 미리 비교할 대상을 생성한다. char b같은 경우에는 black부터 시작하는 체스판의 경우이고 char w는 white부터 시작하는 체스판의 경우이다.

int black(int x, int y);
int white(int x, int y);
char board[50][50];

그리고 black과 white이라는 함수를 선언하는데 black이라는 함수는 위에 미리 선언한 char b와 비교하여 조건에 부합하는 결과를 도출하는 함수이며 white 또한 char w와 비교하여 조건에 부합하는 결과를 도출하는 함수이다. 자세한 설명은 나중에 하겠다.

int main()
{
    int row, columns, result = 123456;
    cin >> row >> columns;

main 함수를 실행하고 실행할 때 row(행)와 columns(열), result(결과)를 선언하고 result는 미리 123456이라고 초기화를 진행했는데 그 이유는 천천히 설명하겠다. 그리고 row와 colums에 각각의 값을 입력을 받는다.

    for (int i = 0; i < row; i++)
        cin >> board[i];

그리고 row(행)만큼 board를 입력한다. 즉, row만큼의 줄을 board에 입력하는 것이다.

   for (int i = 0; i < row - 7; i++)
    {
        for (int j = 0; j < columns - 7; j++)
        {
            result = min(result, min(white(i, j), black(i, j)));
        }
    }
    cout << result << endl;
    return 0;
}

그렇게 되면 이제 우리는 board와 char b, char w끼리 비교를 시작해야 하는데 row와 columns에 7을 뺀 만큼 반복하는 이유는 char b와 char w는 8×8 크기이기에 row와 columns의 크기를 넘지 않은 범위에서 비교하기 위해서 7을 뺐다.

 그리고 여기서 min() 함수는 함수 내에 있는 요소 중에 가장 작은 요소를 반환한다. 예를 들어서 min(1, 2)라고 할 때 1을 반환한다. 그렇다면 white와 black함수에서 반환된 값 중 가장 작은 값을 출력하면 된다. 그리고 마지막에는 result와 비교하여 가장 작은 값을 도출하게 되는데 계속해서 비교하는 시작점이 바뀌기 때문에 이를 기억을 하고 모든 시작점 중 가장 작은 값을 기억하기 위해서 이렇게 result 또한 비교를 진행한 것이고, 그러기 위해서 result의 값을 123456이라는 큰 값으로 미리 초기화를 진행하였다. 그리고 비교한 뒤 그 값을 출력하면 답인데 white와 black에 대해 알아보자.

int white(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] != w[i][j])
                cnt++;
        }
    }
    return cnt;
}

우선 white에 대해 알아보자. white 함수를 살펴보면 cnt를 0으로 초기화시켜준다. 함수 인자인 x와 y는 board의 시작 위치를 가리키는 좌표라고 생각하면 된다. x는 board의 행, y는 board의 열이다. 그 시작 위치에서 가로로 8만큼 세로로 8만큼 비교하기 때문에 board[ x + i ][ y + j ]와 w[ i ][ j ]를 비교하는 것이다. 그리고 만약 다르다면 색을 바꿔 칠 해야 하기 때문에 다른 것이 얼마나 있는지 확인하기 위해 cnt의 값을 1씩 증가시킨다. 그리고 그 값을 반환시켜준다.

int black(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] != b[i][j])
                cnt++;
        }
    }
    return cnt;
}

white 함수와 다른 것은 board와 w를 비교하는 것이 아닌 b와 비교하는 것 말고는 다른 것이 없어서 설명을 생략하겠다.

그래서 결론적으로 이 방법을 정리해보면 다음과 같다.

먼저 해당하는 board의 행과 열을 입력받고 board의 크기를 인식하고 board의 크기만큼 board의 요소들을 채워 넣는다. 그리고 미리 만들어 놓은 white로 시작하는 체스판과 black으로 시작하는 체스판을 board와 비교를 한 뒤에 다른 요소의 개수가 적은 것을 도출해내는 것이다.

3. 느낀 점

처음 예제를 보고 난잡하게 보였는데 역시나 나에게는 어려운 문제였다. 비록 풀이가 매우 간단해 보이지만 고민 끝에 검색을 통해 얻은 해답이라 허탈하기만 하다. 다음에 비슷한 문제를 확인하게 된다면 조금 더 실마리를 확인하고 해결해보도록 노력해야겠다.