체스판 다시 칠하기

Created

2021/08/31 07:19

문제 번호

1018

카테고리

브루트포스

1018번: 체스판 다시 칠하기

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다.

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

Memo

8 \times 8

크기의 체스판 중에서도 최대한 고칠게 없는 올바른 체스판을 찾아내는 것이 목적인데, 시간과 메모리의 크기가 넉넉하고 입력으로 들어오는 체스판 역시

50 \times 50

정도의 크기 밖에 되지 않으므로 완전 탐색이 가능

따라서 올바른 체스판 2 종류를 두고 입력으로 받은 체스판을

8 \times 8

만큼 뜯어서 일일이 찾아보며, 고칠게 가장 적은 타일을 찾아내면 됨

Code

제출 날짜

@8/29/2021

메모리

2024 KB

시간

0 ms

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

const std::vector<std::string>  wb_tile = {
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW"
};
const std::vector<std::string>  bw_tile = {
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB"
};
int                                                             g_answer;
std::pair<int, int>                             g_matrix;
std::vector<std::string>                g_tile;

void    pre_setting(void)
{
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(NULL);
        std::cout.tie(NULL);
}

void    input_action(void)
{
        std::cin >> g_matrix.first >> g_matrix.second;
        g_tile = std::vector<std::string>(g_matrix.first, std::string(g_matrix.second, 0));
        for (auto& i : g_tile)
                for (auto& j : i)
                        std::cin >> j;
        g_answer = 2147483647;
}

int             tile_count(int x, int y, bool is_wb)
{
        int                                                     cnt = 0;
        const std::vector<std::string>& the_tile = is_wb ? wb_tile : bw_tile;

        for (int i = 0; i < 8; ++i)
                for (int j = 0; j < 8; ++j)
                        if (the_tile.at(i).at(j) != g_tile.at(i + x).at(j + y))
                                ++cnt;
        return (cnt);
}

void    solution(void)
{
        for (int i = 0; i + 8 <= g_matrix.first; ++i)
                for (int j = 0 ; j + 8 <= g_matrix.second; ++j)
                        g_answer = std::min({tile_count(i, j, true), tile_count(i, j, false), g_answer});
}

void    output_action(void)
{
        std::cout << g_answer;
}

int             main(void)
{
        pre_setting();
        input_action();
        solution();
        output_action();
        return (0);
}
C++
복사