백준 1018번 체스판 다시 칠하기 C++ 문제풀이

블로그가 있는지 까먹어갈즈음 학교를 졸업하고 백수가 되었네요

프로그래밍 언어나 알고리즘적인 부분에서 많이 약해서 백준 문제풀이를 다시 시작해보려 하는데,
예전에도 그렇고 문제를 풀어갈 때마다, 알고리즘과 자료구조 등 실력적인 부분이 늘어간다기 보다는

이렇게 해도 되나? 싶은 잔머리만 늘어나는 것 같네요. 어쨌든 원하는 결과를 뽑았으니 만족입니다.

 

저도 많이 부족하고 설명도 잘 못하기 때문에, 주석으로 설명이 되어있는 경우 코드적인 부분에서의 자세한 설명은 생략하고 접근한 아이디어만 간략히 소개해 드리겠습니다. +예전에 풀었던 문제들은 나중에 천천히 올리도록 하겠습니다.

 

 

///////

 

1018번 문제는 체스판 다시 칠하기 문제로,

최대 50by50 배열에서 임의의 8by8 배열을 선택해서 요구조건을 충족하려면 몇 개의 칸을 다시 칠해야 하는지를 카운팅 해줘야 하는 상당히 악질적인 문제입니다.

 

WBWBWBWB

BWBWBWBW 이런식으로 상하좌우와 같은 색이 되지 않도록 모든 칸을 칠해줘야 하는데, 옛날에 확률과 통계에서 영역별 색을 칠하는 비슷한 문제를 풀었던 기억이 나네요.

 

또한 W로 시작해서 WBWBWBWB 로 이어지는 경우와 B로 시작해서 BWBWBWBW 로 이어지는 2가지 경우 모두 고려해줘야 합니다.

 

제가 접근한 방식은, 주어진 배열에서 우리가 고를 수 있는 체스판은 한정되어 있기 때문에, 모든 체스판을 계산해봐도 시간복잡도가 엄청나게 늘어나지는 않겠거니 하고 전수조사해봤습니다..

 

(체스판은 8x8 배열로 고정된 크기이기에

최대 MxN 크기인 보드 내에서 왼쪽 최상단을 원점으로 두고 M-8 x N-8 크기 의 부분적인 배열을 상정하여

해당 부분 배열 내 아무 원소나 골라 해당 원소를 8x8 체스판의 시작점으로 설정해 계산하면 된다는 것이겠죠)

 

위 설명은 몰라도 되고,

아래의 numfix 함수에는 50by50 배열 중 어느 위치에서부터 체스판이 시작될지 전달해줍니다.

해당 위치부터 우로 8칸, 하로 8칸을 체스판으로 상정하여 계산을 시작합니다.

 

W로 시작하는 체스판의 경우,

WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

좌상단의 첫 번째 W의 좌표를 (0, 0), 우하단의 마지막 W의 좌표를 (7, 7) 로 생각하고 (배열 인덱스와 동일)

 

공통점을 찾아보니, 짝수번째 row에서는 짝수번째 column 마다 W가 등장하고, 홀수번째 row에서는 홀수번째 col 마다 등장하네요.

 

이것을 기반으로 row%2 와 col%2 의 값이 같은 경우, 배열 원소의 값이 W가 아니라면 잘못 칠해졌다고 생각할 수 있습니다.

 

row%2 와 col%2 의 값이 같지 않은 경우엔, W가 나와서는 안되니 B 가 나와야 합니다. 이 경우 B가 아닌 경우 잘못 칠해였다고 생각합니다.

 

이런 방식으로 원하는 8x8 배열에서 잘못 칠해진 칸이 몇 개 있는지 카운팅해줬습니다.

 

다만, 이 경우 첫 칸이 W인 경우에 한해서만 정확한 카운팅이 가능합니다.

따라서 B가 첫 칸인 경우의 값도 구해주는데,

이는 간단하게 W가 시작인 체스판을, B가 시작인 체스판을 기준으로 카운팅했을 경우

64개의 잘못 칠해진 부분이 검출될것이고, 따라서 검출값에서 64를 빼주면(수를 반전시켜주면) 반대상황에서의 검출값이 나올거같아서 그렇게 구했습니다. 계산한 검출값들 중 작은 값을 선택해 반환해줍니다.

 

위의 numfix 함수를 선택할 수 있는 모든 체스판들에 대해 수행해 최소값을 출력해주니 풀렸습니다.

 

제가 잘못 풀이한 부분이나 궁금한 내용 있다면 댓글로 남겨주세요, 폰에 연동되어 있어서 생각보다는 빠르게 피드백 가능합니다.

#https://itre.tistory.com/
#include <iostream>
using namespace std;

char arr[50][50];

int numfix(int rowpivot, int colpivot)
{
    int prew, preb = 0;
    int row, col = 0;

    //초기화 후 첫 칸이 W인 체스판을 기준으로 몇 개의 칸을 수정해야 하는지 계산한다.
    //인자인 row와 col의 pivot값은 n by m 배열에서 어느 위치의 8by8 배열인지를 나타내는 값들이며 (= 8by8 배열 시작지점의 원소 위치)
    //W를 기준으로 계산한 값을 이용해 B를 기준으로 계산할 경우도 구해보며 그 중 작은 값을 선택해 반환함
    row = 0;
    prew = 0;
    preb = 0;
    for (int i = rowpivot; i < rowpivot + 8; i++)
    {
        for (int j = colpivot; j < colpivot + 8; j++)
        {
            if ((row % 2) == (col % 2))
            {
                if (arr[i][j] != 'W')
                {
                    prew++;
                }
            }
            else
            {
                if (arr[i][j] != 'B')
                {
                    prew++;
                }
            }
            col++;
        }
        col = 0;
        row++;
    }

    preb = 64 - prew;

    if (prew >= preb)
        prew = preb;

    return prew;
}

int main(void)
{
    int n, m = 0;

    // n = row, m = column
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }

    //n by m 배열에서 각 row와 col에 8을 빼준 값만큼 row와 col을 탐색하며 계산한다.
    int movrow = n - 8;
    int movcol = m - 8;

    //모든 가능한 배열들에서 계산한 값들 중 가장 작은 값을 temp로 두고 출력한다.
    int temp= 64;
    int num = 0;
    for (int i = 0; i <= movrow; i++)
    {
        for (int j = 0; j <= movcol; j++)
        {
            num = numfix(i, j);
            if (temp >= num)
                temp = num;
        }
    }

    cout << temp;
}