[C#] 백준 1018번 문제풀이

안녕하세요.

백준 1018번 '체스판 다시 칠하기' 문제풀이를 진행해보도록 하겠습니다.

해당 문제는 체스판중 다시 칠해야하는 부분이 가장 적은 8x8배열을 몇번 다시 칠했는지를 출력하는 문제입니다.

이번에는 브루트포스 알고리즘을 사용하여 풀어야하기 때문에 시간이 많이 걸린 편이고, GPT에게 많이 배웠습니다.

입력예제

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

 

출력예제

1

 

먼저, 입력을 받아오겠습니다. 체스판의 총 크기 (N,M)을 받아옵니다.

아래에 보드(체스판) 이중배열을 선언해주고 크기를 N,M으로 지정해줍니다.

입력으로 들어온 각 칸의 색상을 board에 채워 넣습니다.

string[] size = Console.ReadLine().Split();
int N = int.Parse(size[0]);
int M = int.Parse(size[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];
    }
}

 

다음으로, 답 변수(minCount)를 선언합니다. 더 적은수가 들어올경우 값을 바꿔야하기 때문에 int.MaxValue 값으로 초기하시켜줍니다. for 반복문으로 모든 8x8 배열의 시작점과 보드를 CountRepaint 메서드의 값으로 호출합니다.

반복문이 N - 8인 이유는 주어진 체스판 크기 안에서 8x8 경우의 수를 찾아야하기 때문입니다.

메서드로 돌아온 경우의 수가 minCount보다 작다면 minCount의 값을 바꿉니다.

이런식으로 모든 8x8 체스판 배열의 시작점으로 CountRepaint메서드를 호출하다보면 최종적으로 가장 적게 다시 칠할 수 있는 값이 minCount에 담기고, 이 값을 출력하면 답이 나옵니다.

int minCount = int.MaxValue;

for (int i = 0; i <= N - 8; i++)
{
    for (int j = 0; j <= M - 8; j++)
    {
        int count = CountRepaint(board, i, j);
        minCount = Math.Min(minCount, count);
    }
}

Console.WriteLine(minCount);

 

이제 CountRepaint 메서드를 작성해보도록 하겠습니다.

먼저, 값으로 보드와 시작x좌표, 시작y좌표를 받아옵니다.

시작점을 중심으로 가로세로 8 길이의 보드를 탐색합니다.

만약 예측한 칸의 색상과 현재 색상이 다르다면, 카운트를 증가시킵니다.

시작점이 검은색일때와 하얀색일때의 카운트중 더 적은것을 반환시킵니다.

    static int CountRepaint(char[,] board, int startX, int startY)
    {
        int wStart = 0;
        int bStart = 0;

        for (int i =0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                char curent = board[startX + i, startY + j];
                bool isEven = (i + j) % 2 == 0;

                if (isEven)
                {
                    if (curent != 'W') wStart++;
                    if (curent != 'B') bStart++;
                }
                else
                {
                    if (curent != 'B') wStart++;
                    if (curent != 'W') bStart++;
                } 
            }
        }

        return Math.Min(wStart, bStart);

 

지금까지 풀었던 실버 4중 가장 복잡했던 것 같아요😵😵

다음은 전체코드입니다.

 

전체코드

using System;

class Program
{
    static void Main()
    {
        string[] size = Console.ReadLine().Split();
        int N = int.Parse(size[0]);
        int M = int.Parse(size[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 minCount = int.MaxValue;

        for (int i = 0; i <= N - 8; i++)
        {
            for (int j = 0; j <= M - 8; j++)
            {
                int count = CountRepaint(board, i, j);
                minCount = Math.Min(minCount, count);
            }
        }

        Console.WriteLine(minCount);
    }

    static int CountRepaint(char[,] board, int startX, int startY)
    {
        int wStart = 0;
        int bStart = 0;

        for (int i =0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                char curent = board[startX + i, startY + j];
                bool isEven = (i + j) % 2 == 0;

                if (isEven)
                {
                    if (curent != 'W') wStart++;
                    if (curent != 'B') bStart++;
                }
                else
                {
                    if (curent != 'B') wStart++;
                    if (curent != 'W') bStart++;
                } 
            }
        }

        return Math.Min(wStart, bStart);
    }
}