BOJ 1018 – 체스판 다시 칠하기

문제 설계

N×M 보드에서

8×8 부분 보드를 선택해 체스판 규칙(W/B 번갈아)을 만족하도록

최소 수정 횟수를 구하는 문제.

각 8×8은 시작 색이 W 또는 B인 두 가지 경우만 존재.

 

생각한 문제 패턴

브루트포스 + 패턴 매칭 문제라고 판단.

8×8로 자르는 모든 경우를 검사해야 하며, 색 배치 규칙이 반복됨.

 

첫 접근했을때 생각

왼쪽 위 기준으로만 세면 오른쪽 아래에 있는 색을 놓칠 수 있다고 생각함.

그래서 왼쪽 위 기준 / 오른쪽 아래 기준을 각각 따로 세야 한다고 판단함.

 

알고리즘

왼쪽 위를 기준으로 체스판 패턴과 비교하여

mismatch 개수 계산오른쪽 아래를 기준으로 역방향으로

다시 mismatch 계산 두 결과 중 최소값을 선택하려고 함.

 

// if(array[i][j] == 'W')
// {
// 	for(int k =0; k<8; k++)
// 	{
// 		for(int l = 0; l<8; l++){

// 			if(array[i+k][j+l] != ((k+l)%2==0 ? 'W' : 'B'  ))
// 			{
// 				cntdif++;
// 			}

// 		}
// 	}
// }

// else if(array[i][j] =='B')
// {
// 	for(int k =0; k<8; k++)
// 	{
// 		for(int l = 0; l<8; l++){

// 			if(array[i+k][j+l] != ((k+l)%2==0 ? 'B' : 'W'  ))
// 			{
// 				cntdif++;
// 			}

// 		}
// 	}
// }

// int cntdif1 =0;
// if(array[i+7][j+7] == 'W')
// {
// 	for(int k=0; k>-8; k--)
// 	{
// 		for(int l =0; l>-8; l--)
// 		{
// 			if(array[i+7 + k][j + 7 + l] != ((k+l)%2==0 ? 'W' : 'B'  ))
// 			{
// 				cntdif1++;
// 			}
// 		}
// 	}

// }

// else if(array[i+7][j+7] == 'B')
// {
// 	for(int k=0; k>-8; k--)
// 	{
// 		for(int l =0; l>-8; l--)
// 		{
// 			if(array[i+7 + k][j + 7 + l] != ((k+l)%2==0 ? 'B' : 'W'  ))
// 			{
// 				cntdif1++;
// 			}
// 		}
// 	}

// }


// int dif = cntdif<cntdif1 ? cntdif : cntdif1;

// if(dif<min) min = dif;

 

잘못됨 판단 신호

코드가 복잡해지고 분기(if)가 과도하게 늘어남.

역방향 순회 시 parity((k+l)%2) 기준이 직관과 다르게 작동하며

결과 신뢰가 떨어짐.

생각보다 로직이 설명되지 않는 느낌이 강해짐.

 

해결 방법

각 8×8 영역에서 • W로 시작하는 체스판 패턴과의 mismatch 개수 

B로 시작하는 체스판 패턴과의 mismatch 개수 를 가정하여

각각 계산하고 둘 중 최소값을 사용.

 

int min = 100;

for(int i=0; i<=N-8; i++ )
{
    for(int j=0; j<=M-8; j++)
    {
        int cntW = 0;
        int cntB = 0;

        for(int a= 0; a<8; a++)
        {
            for(int b = 0; b<8; b++)
            {
                char cur = array[i+a][j+b];

                if((a+b)%2 ==0)
                {
                    if(cur == 'W') cntB++;
                    else if( cur =='B') cntW++;
                }
                else if((a+b)%2 !=0)
                {
                    if(cur =='B') cntB++;
                    else if(cur =='W') cntW++;
                }
            }
        }
    }
}

 

배운점

좌표·방향 문제가 아니라 상태(패턴) 문제임.

어디서 세느냐가 아니라 어떤 패턴을 가정하느냐가 핵심.

대칭이나 반대 방향을 따로 고려할 필요가 없다는 것을 배웠다