[C] 백준 | 1018번 코드 - 체스판 다시 칠하기

>문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

> 핵심

(0,0) 지점 색깔을 반대로 칠하는 경우도 고려하자!

>풀이과정

코드를 다 짜놓고 예제를 돌려보니 다 맞게 나오는데 제출을 하면 오답이 나왔다.

왜인가 싶어서 질문 게시판에 반례를 찾아 넣어보니 오답이 툭 튀어나왔다.

대체 왜그런가.. 한참을 고민했는데 문득 스쳐지나간 생각.

 

(0,0)점 색을 바꾸는 경우도 있겠구나!!! 뜨악!

 

나는 그것도 모르고 몇십분동안 되도않는 디버깅을 하면서 뭐가 문제인가 어디서 꼬였나 끙끙대고 있었다. 어휴.

아무튼 (0,0)점을 'B'로 칠하는 경우와 (0,0)점을 'W' 로 칠하는 경우 모두를 고려해야 한다.

 

우선 ar[50][50] 배열에 값을 입력받고, 원하는 지점부터 8x8 사이즈로 잘라 tmp[8][8] 배열에 복사해 넣는다.

그 이후 check_color 함수에서 (0,0) 지점부터 (8,8) 지점까지 반복문으로 순회하며 색을 칠하는 횟수를 센다.

 

(0,0) 점을 기준으로 현재 색이 'B' 라고 가정하면, (i+j) % 2 가 0인 점도 모두 'B' 이어야 하고, 이외에는 모두 'W'.

그리고 (0,0)점의 색을 반대로 칠하는 경우를 고려해 다시 한번 반복문을 돌며 숫자를 센다.

 

 

#이 문제를 통해 다시 배운 것

1. 이차원 배열을 함수인자로 넘기는 방법

- 이차원 배열을 함수인자로 넘길때는 char ar[][8] 과 같이 쓰거나, char (*ar)[8] 과 같이 써야한다.

- 이중포인터 char **ptr , 혹은 모든 칸이 빈 char [ ][ ] 으로 받을 수 없다!!

 

2. 포인터로 이차원 배열 가리키는 방법.

int ar[2][4] = {{1,2,3,4},{5,6,7,8}};
int (*ptr)[4] = ar;

for(i=0; i<2; i++)
{
    for(j=0; j<4; j++)
    {
    	printf("%d,",ptr[i][j]);
    }
    printf("\n");
}

- int (*ptr)[4] 는 int [4]를 가리키는 포인터

 

3. 이차원 배열 int ar[2][4] 는 겉보기에는 int ar[4] 배열이 2층으로 쌓여있을 것 같은데 사실은 선형적으로 이어져있다.

-> 형 변환을 통해 선형적으로 풀어서 가리켜도 된다!

int ar[2][4];
int *ptr = (int *)ar

 

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int check_color(char ar[][8])
{
	int i, j, cnt = 0, cnt2 = 1, min;

	for (i = 0; i < 8; i++)
	{
		for (j = 0; j < 8; j++)
		{
			if ((i + j) % 2 == 0 && ar[i][j] != ar[0][0])
			{
				cnt += 1;
			}
			else if ((i + j) % 2 != 0 && ar[i][j] == ar[0][0])
			{
				cnt += 1;
			}
		}
	}

	ar[0][0] = ar[0][0] == 'B' ? 'W' : 'B';

	for (i = 0; i < 8; i++)
	{
		for (j = 0; j < 8; j++)
		{
			if ((i + j) % 2 == 0 && ar[i][j] != ar[0][0])
			{
				cnt2 += 1;
			}
			else if ((i + j) % 2 != 0 && ar[i][j] == ar[0][0])
			{
				cnt2 += 1;
			}
		}
	}

	min = cnt < cnt2 ? cnt : cnt2;
	return min;
}

void cutting(char ar[][50], char tmp[][8], int i, int j)
{
	for (int y = 0; y < 8; y++)
	{
		for (int x = 0; x < 8; x++)
		{
			tmp[y][x] = ar[i + y][j + x];
		}
	}
}

int main()
{
	char ar[50][50];
	char tmp[8][8];
	int M, N, i, j, cnt, min;

	scanf("%d %d", &M, &N);

	for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			scanf(" %c", &ar[i][j]);
		}
	}

	min = M * N;

	for (i = 0; i <= M - 8; i++)
	{
		for (j = 0; j <= N - 8; j++)
		{
			cutting(ar, tmp, i, j);
			cnt = check_color(tmp);

			if (cnt < min)
				min = cnt;

		}
	}
	printf("%d\n", min);

	return 0;
}