백준 1018 C#) 체스판 다시 칠하기

구현이 조금 까다로울 수도 있는 문제다.

 

public static class PS
{
    private static int m, n;
    private static char[][] board;

    static PS()
    {
        string[] mn = Console.ReadLine().Split();
        m = int.Parse(mn[0]);
        n = int.Parse(mn[1]);

        board = new char[m][];

        for (int i = 0; i < m; i++)
        {
            board[i] = Console.ReadLine().ToCharArray();
        }
    }
    public static void Main()
    {
        int min = 32;

        for (int row = 0; row <= m - 8; row++)
        {
            for (int col = 0; col <= n - 8; col++)
            {
                min = Math.Min(min, Check(row, col));
            }
        }

        Console.Write(min);
    }

    private static int Check(int startRow, int startCol)
    {
        (int a, int b) count = (0, 0);

        for (int row = 0; row < 8; row++)
        {
            for (int col = 0; col < 8; col++)
            {
                switch ((row + col) % 2)
                {
                    case 0:
                        if (board[startRow + row][startCol + col] != board[startRow][startCol])
                            count.a++;
                        else
                            count.b++;
                        break;

                    case 1:
                        if (board[startRow + row][startCol + col] == board[startRow][startCol])
                            count.a++;
                        else
                            count.b++;
                        break;
                }
            }
        }

        return Math.Min(count.a, count.b);
    }
}

 

우선, 나는 입력을 가변 배열에 저장했다.

보통은 입력 사이에 공백이 없을 경우 한 문자씩 읽어 일일이 2차원 배열에 저장하곤 하는데

이번에는 그냥 ToCharArray 메소드를 사용하여 한번에 저장하도록 하였다.

 

입력을 다 받았으면 이제 모든 경우의 수를 체크해야 하는데, 나는 각 경우의 수마다 기준이 되는 지점을 8x8 체스판의 좌측 상단으로 정했다.

그러면 좌측 상단이 가질 수 있는 값의 범위는 행 : [0, m-8], 열 : [0, n-8] 이 된다. 이 범위에 존재하는 모든 경우의 수를 체크해야 한다.

(이해가 안된다면 주어진 보드에서 8x8 크기의 정사각형이 왔다갔다 한다고 생각해보자)

 

기준을 좌측 상단으로 잡았다면 계산은 아주 간단하다. 그냥 좌측 상단부터 8x8 크기를 일일이 훑어보면 된다...

단, 여기서도 두 가지 경우가 존재한다. 기준점의 색을 바꾸지 않는 경우와 바꾸는 경우다.

만약 바꾸지 않는 경우가 최솟값이 되려면 기준점으로부터 짝수칸 떨어진 곳은 최대한 기준점과 같아야 할 것이고, 홀수칸만큼 떨어진 곳은 최대한 기준점과 달라야 할 것이다.

그렇게 두 경우를 모두 구하여 작은 값을 취하고, 이어서 모든 8x8 체스판에 대해서도 작은 값을 취하면 되겠다.

(참고로 하나의 경우만 구해도 답은 구할 수 있는데 큰 차이는 없으므로 각자 알아서 직관적인 방법을 택하자)