[BOJ] 체스판 다시 칠하기 (미해결) - 해결

일단 첫번째 테스트 케이스 처럼 8X8 사이즈의 체스판케이스에서 칠해야하는 블럭들의 최소숫자는 구할수 있었다.

기본적으로 흰색으로 시작할때와 검은색으로 시작할때 두가지 경우를 대상 8X8 체스 보드와 비교하여 새로 칠해야하는 블럭의 숫자가 더 낮은 경우를 출력시키면 되는것이니 해당 구현은 완료했으나  그보다 큰 체스판일때의 경우의 수를 어떤식으로 구현하면 좋을지에서 막혔다;;

using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

namespace Assignment01
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] whitStart = 
            {
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW" 
            };
            string[] blackStart = 
            {
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB"
            };

            int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            string[] chessBoard = new string[NM[0]];

            for(int i = 0; i < NM[0]; i++)
            {
                chessBoard[i] = sr.ReadLine();                          
            }

            int cnt = 0;
            int cnt2 = 0;
                                              
                int temp2 = 0;
                int temp3 = 0;
                for (int i = 0; i < NM[0]; i++)
                {
                    for (int j = 0; j < NM[1]; j++)
                    {                        
                        if (chessBoard[i][j] != whitStart[temp2][temp3])  cnt++;  
                        if (chessBoard[i][j] != blackStart[temp2][temp3]) cnt2++; 
                    }
                }
                                                                                                   
            sw.WriteLine(cnt);
            sw.WriteLine(cnt2);
            sw.WriteLine(Math.Min(cnt, cnt2));

            sr.Close();
            sw.Close();
        }
    }
}

결과창

 

이제 남은건 8X8  이 넘어가는 케이스들에 대해 해결하면 되는건데....흠.... 좀더 고민해 보기로

 

하고 오늘 다시보니

체스판에서 나올수 있는 8X8 배열의 체스판들을 모두 구해주는 걸 구현할수 있었다.

4중 for문을 돌며 해결했는데 일단 테스트케이스에 입력된 체스보드의 각 가로 세로 크기에서 7을 뺀 숫자 들을 곱한 만큼의 경우의 수가 나온다는걸 알수 있었다.

해당 로직을 구현하기 위해 새로운 for문을 추가하였고 해당 for문에서 각 케이스별로 나온 최소 숫자를 정수 변수 min에 담아 비교하며 최소 숫자를 구하는 방식을 이용하여 해결하였다.

 

문제풀이

using System;
using System.IO;

namespace Assignment01
{
    class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] whitStart =  // 화이트 체스보드 기본형 8X8
            {
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW"
            };
            string[] blackStart =// 블랙 체스보드 기본형 8X8
            {
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB",
                "BWBWBWBW",
                "WBWBWBWB"
            };

            int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse); // 입력받은 가로 세로 크기 숫자를 정수 배열에 담아주고
            string[] chessBoard = new string[NM[0]];    //입력받은 숫자의 세로 숫자만큼의 스트링 배열을 생성

            for (int i = 0; i < NM[0]; i++) //배열의 인덱스에 입력된 테스트케이스 요소 할당
            {
                chessBoard[i] = sr.ReadLine();
            }


            int min = 10000;   // 최소숫자 초기화

            for (int k1 = 0; k1 < NM[0] - 7; k1++)   //입력된 세로 크기 -7 (기본형의 크기가 8이기 떄문에) 만큼 순회
                for (int k2 = 0; k2 < NM[1] - 7; k2++) // 입력된 가로 크기 -7 (기본형의 크기가 8이기 떄문에) 만큼 순회
                {
                    int cnt = 0;   // 화이트 체스보드 기본형일 경우 다시칠해야할 사각형 숫자 초기화
                    int cnt2 = 0; // 블랙 체스보드 기본형일 경우 다시칠해야할 사각형 숫자 초기화
                    for (int i = 0; i < 8; i++)  // for문을 돌며 기본형과 비교 (세로 인덱스) 세로인덱스의 요소별로 비교
                    {
                        for (int j = 0; j < 8; j++) //for문을 순회하며 비교
                        {
                            if (chessBoard[i + k1][j + k2] != whitStart[i][j]) cnt++;
                            if (chessBoard[i + k1][j + k2] != blackStart[i][j]) cnt2++;
                        }
                    }
                    if (cnt < min)  //최소 숫자 의 비교 후 초기화
                        min = cnt;
                    if (cnt2 < min)
                        min = cnt2;
                }


            sw.WriteLine(min);   //최소숫자 출력

            sr.Close();
            sw.Close();
        }
    }
}

 결과창

경우의 수를 구하는걸 구현하는게 조금 까다로웠던거 같다. 생각으로만 하기엔 좀 어려워 그림으로 무식하게 그려가면서 이해하는게 제일 베스트였던 브루트 포스 문제였다;;