Written by JS970
on November 1, 2022

1018 - 체스판 다시 칠하기

난이도: 실버 4
날짜: 2022년 11월 1일
상태: Correct
추가 검토 여부: No

solution

모든 경우의 수를 검색하는 부르트포스 알고리즘 문제였다.
정답 체스판 배열, 입력된 값을 8x8크기로 자르는 함수, 8x8크기로 조정된 입력과 정답을 비교하는 함수를 이용
정답 체스판 배열의 경우 8x8크기로 고정하여 전역변수로 선언하였다.
입력을 8x8크기로 자르는 함수의 경우 동적 할당을 사용하여 새로운 배열을 이중 포인터 형태로 반환한다.
정답을 비교하는 함수는 8x8크기의 두 배열에 대해 불일치 지점의 개수를 세는 역할을 한다.
각각을 구현하니 프로그램이 정답을 출력함을 확인할 수 있었다.

code

#include <iostream>
using namespace std;

int real_chessboard[8][8] = { 1, 0, 1, 0, 1, 0, 1, 0,
                              0, 1, 0, 1, 0, 1, 0, 1,
                              1, 0, 1, 0, 1, 0, 1, 0,
                              0, 1, 0, 1, 0, 1, 0, 1,
                              1, 0, 1, 0, 1, 0, 1, 0,
                              0, 1, 0, 1, 0, 1, 0, 1,
                              1, 0, 1, 0, 1, 0, 1, 0,
                              0, 1, 0, 1, 0, 1, 0, 1 };

int** cut(int **cb, int rowidx, int colidx)
{
    int **size8x8 = new int*[8];
    for (int i = 0; i < 8; i++)
        size8x8[i] = new int[8];

    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            size8x8[i][j] = cb[rowidx+i][colidx+j];

    return size8x8;
}

int fix(int **cb)
{
    int count = 0, todofix;

    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            if (cb[i][j] != real_chessboard[i][j]) count++;

    todofix = (count <= 32) ? count : 64-count;
    return todofix;
}

int main()
{
    int row, column;
    cin >> row;
    cin >> column;

    int **chessboard = new int*[row];
    for (int i = 0; i < row; i++)
        chessboard[i] = new int[column];

    char color;
    int clr;
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            cin >> color;
            // White --> 1, Black --> 0
            clr = (color == 'W') ? 1 : 0;
            chessboard[i][j] = clr;
        }
    }

    int minfix = 65;
    int tmp;
    for (int i = 0; i < row - 7; i++)
    {
        for (int j = 0; j < column - 7; j++)
        {
            tmp = fix(cut(chessboard, i, j));
            if (tmp < minfix) minfix = tmp;
        }
    }

    cout << minfix << endl;
    return 0;
}

int **arr = new int*[row]
for (int i = 0; i < row; i++)
	arr[i] = new int[col];

ref

1018번: 체스판 다시 칠하기

Top