백준 - [단계별로 풀어보기 브루트 포스] 1018 체스판 다시 칠하기

이번 문제는 꽤 오랫동안 고민했던 문제였다. 결국 여러 코드와 해설을 찾아보며 참고했고, 이를 바탕으로 직접 구현해 보았다.

브루트포스 방식으로 값을 하나씩 대입해 검사하는 접근 자체는 어렵지 않았다.
하지만 8 × 8 범위의 체스판을 검사하면서 최소로 다시 칠해야 하는 칸의 수를 구하는 과정에서 범위를 어떻게 설정해야 할지 감을 잡지 못했다. 특히 전체 N × M 체스판에서 어떤 위치를 기준으로 8 × 8 영역을 검사해야 하는지에 대해 한동안 고민하게 되었다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    internal class BruteForce
    {
        static void Main(string[] args)
        {
            // 1018 체스판 다시 칠하기
            string[] inputSize = Console.ReadLine().Split();
            int N = int.Parse(inputSize[0]);
            int M = int.Parse(inputSize[1]);

            char[,] board = new char[N, M];

            // 체스판의 각 줄을 입력받아 배열에 저장
            for (int i = 0; i < N; i++)
            {
                string line = Console.ReadLine();
                for (int j = 0; j < M; j++)
                {
                    board[i, j] = line[j];
                }
            }
            // 최소로 다시 칠해야 하는 칸 수를 저장
            int result = int.MaxValue;

            // N×M 체스판에서 8×8 크기의 체스판을 만들 수 있는 모든 시작 위치 검사
            for (int i = 0; i <= N - 8; i++)
            {
                for (int j = 0; j <= M - 8; j++)
                {
                    // 시작 색이 흰색일 때 다시 칠해야 하는 칸 수
                    int whiteStart = 0;
                    // 시작 색이 흰색일 때 다시 칠해야 하는 칸 수
                    int blackStart = 0;

                    // 현재 위치에서 8×8 영역 검사
                    for (int x = 0; x < 8; x++)
                    {
                        for (int y = 0; y < 8; y++)
                        {
                            // 체스판은 (행+열)이 짝수일 때 시작 색과 같아야 한다
                            if ((x + y) % 2 == 0)
                            {
                                // 흰색 시작 체스판일 때 현재 칸이 W가 아니면 다시 칠해야 함
                                if (board[i + x, j + y] != 'W') whiteStart++;
                                // 검은색 시작 체스판일 때 현재 칸이 B가 아니면 다시 칠해야 함
                                if (board[i + x, j + y] != 'B') blackStart++;
                            }
                            else
                            {
                                // 검은색 시작 체스판일 때 현재 칸이 B가 아니면 다시 칠해야 함
                                if (board[i + x, j + y] != 'B') whiteStart++;
                                if (board[i + x, j + y] != 'W') blackStart++;
                            }
                        }
                    }

                    // 두 경우(흰색 시작, 검은색 시작) 중 더 적게 칠하는 경우 선택
                    result = Math.Min(result, Math.Min(whiteStart, blackStart));
                }
            }

            // 두 경우(흰색 시작, 검은색 시작) 중 더 적게 칠하는 경우 선택
            Console.WriteLine(result);
        }
    }
}

출력 결과1

출력 결과2

출력 결과3

여러 코드와 해설을 살펴보니 N × M 체스판에서 8 × 8 크기의 체스판을 만들 수 있는 모든 시작 위치를 기준으로 검사를 해야 한다는 것을 알게 되었다.

결국 이 문제는 처음부터 스스로 풀어내지는 못했고, 다른 풀이를 참고해 구현하는 데에 그치게 되었다. 하지만 나중에 이 문제와 비슷한 유형의 문제를 접하거나 다시 이 문제를 보게 되었을 때는 스스로 해결할 수 있도록 더 다양한 문제들을 경험해 봐야겠다고 생각했다.

---

참고

백준 1018 체스판 다시 칠하기 [JAVA]

 

[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]

 

백준 1018 체스판 다시 칠하기