[C#] 1018번: 체스판 다시 칠하기

목차

---

백준 단계별로 풀어보기

25.10.11

12단계: 브루트 포스

1018번: 체스판 다시 칠하기

문제 링크 : https://www.acmicpc.net/problem/1018

 

문제 풀이

>> 문제를 풀기 위해 알아야 할 개념

- 문제 이해

• M×N 크기의 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. --> 어느 한 점을 기준으로 8×8 크기를 고른다.
• 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 체스판을 색칠하는 경우는 맨 왼쪽 위 칸이 흰색인 경우와 검은색인 경우로 두 가지 뿐이다. --> 기준으로 삼은 칸이 흰색일 경우와 검은색일 경우를 고려해야 한다.

 

>> 기준점을 찾는 과정

: 8×8 크기의 체스판에서 맨 왼쪽 위 칸을 기준으로 삼을 때, 기준칸이 될 수 있는 좌표는 아래 그림과 같이 (0, 0)에서부터 (M - 8, N - 8)까지이다.

 

>> 짝수 칸과 홀수 칸의 규칙

: 8×8 크기의 체스판에서 맨 왼쪽 위 칸을 기준으로 삼고 이를 (0, 0)으로 본다면, 아래 그림과 같이 (0, 0)을 기준으로 짝수 칸과 홀수 칸은 다음과 같은 규칙을 따른다.

• 짝수 칸은 기준 칸과 동일한 색이어야 한다.
• 홀수 칸은 기준 칸과 다른 색이어야 한다.

--> (x, y)에서 (x + y) % 2 의 값이 0이면 짝수 칸, 1이면 홀수 칸이다. 즉, (x + y) % 2로 구하는 짝수 칸과 홀수 칸은 기준 칸에 대해 상대적인 칸이다.

--> 기준 칸이 흰색인 경우와 검은색인 경우 모두 고려해야 한다.

 

>> 풀이

1. M과 N 값을 입력받아 int값으로 변환하고, board값을 받아 저장할 char 형식의 2차원 배열 board를 선언하고, 최솟값을 담을 변수 min을 최댓값으로 초기화한다.
2. 이중 for문을 활용하여 board값을 받아 2차원 배열 board에 저장한다.
3. 이중 for문을 활용하여 보드를 자를 기준점을 돌며 색을 칠하는 최솟값을 찾는다.
   •     기준 칸이 될 수 있는 (0, 0)부터 (M - 8, N - 8)까지 이중 for문을 반복한다.
   •     기준 칸이 흰색('W')일 때 다시 칠해야 하는 칸 수를 담을 변수 wCount를 초기화한다.
   •     기준 칸이 검은색('B')일 때 다시 칠해야 하는 칸 수를 담을 변수 bCount를 초기화한다.
4. 현재 기준 칸에 대해 이중 for문을 활용하여 8×8 크기의 체스판을 돌며 switch문을 활용하여 현재 칸이 짝수 칸인지, 홀수 칸인지에 따라 기준 칸과의 색을 비교하고 색을 칠해야 하면 해당 색에 맞는 Count를 증가시킨다.
   
   •     (row + col) % 2 값이 0이라면 짝수 칸이므로 기준 칸과 색이 같아야 한다.
     •     만약 기준 칸이 'W' 인데 현재 칸이 'W'가 아니라면, wCount를 증가시킨다.
     •     만약 기준 칸이 'B' 인데 현재 칸이 'B'가 아니라면, bCount를 증가시킨다.
   •     (row + col) % 2 값이 1이라면 홀수 칸이므로 기준 칸과 색이 달라야 한다.
     •     만약 기준 칸이 'W' 인데 현재 칸이 'B'가 아니라면, wCount를 증가시킨다.
     •     만약 기준 칸이 'B' 인데 현재 칸이 'W'가 아니라면, bCount를 증가시킨다.
5. 현재 기준 칸에 대해 wCount와 bCount 를 모두 구한 뒤, 둘 중 최솟값을 찾고, 찾은 최솟값이 기존 최솟값보다 작다면 갱신해준다.
6. 모든 기준점을 돌며 찾은 최솟값을 출력한다.

 

정답 코드

class Backjoon
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
        char[,] board = new char[n, m];
        int min = int.MaxValue;
            
        for (int i = 0; i < n; i++)
        {
            string line = Console.ReadLine();
            for (int j = 0; j < m; j++)
            {
                board[i, j] = line[j];
            }
        }

        for (int y = 0; y <= n - 8; y++)
        {
            for (int x = 0; x <= m - 8; x++)
            {
                int wCount = 0;
                int bCount = 0;
                for (int row = y; row < y + 8; row++)
                {
                    for (int col = x; col < x + 8; col++)
                    {
                        switch ((row + col) % 2)
                        {
                            case 0:
                                if (board[row, col] != 'W') wCount++;
                                if (board[row, col] != 'B') bCount++;
                                break;
                            case 1:
                                if (board[row, col] != 'B') wCount++;
                                if (board[row, col] != 'W') bCount++;
                                break;
                        }
                    }
                }
                int count = Math.Min(wCount, bCount);
                if (count < min) min = count;
            }
        }
        Console.Write(min);
    }
}