브루트 포스 - 1018번

1월 13일(금) - 브루트 포스(1018번)

1018번: 체스판 다시 칠하기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

12일날 다 풀지 못했던 부분에서 이어서 진행

https://jh4995.tistory.com/98

1월 12일(목) - 브루트 포스(1018번)

문제점

1. %s로 입력받으면서 전체 입력이 제대로 진행되지 않는 것을 발견

-> 이중 for 문에서 %c로 받으면서 해결 + scanf(" %c", ) 로 "빈칸" 만들어야함 -> 이 부분때문에 개고생

 

2. 보드의 처음이 B인 경우와 W인 경우를 4중 for 문 안에서 다시 if 문을 사용해서 비교하는 것은 너무 복잡함

-> B로 8x8 보드가 시작하는 blcak_start 와 W로 8x8 보드가 시작하는 white_start 배열을 만든 뒤에,

    입력받은 보드와 각각 비교해보면서 change_to_W와 change_to_B를 카운팅하는 것으로 변경

 

3. change_to_W 와 change_to_B 의 대소비교하는 과정이 너무 조잡함

-> if 와 else 구조로 변경한 뒤, change_count 변수에다가 두 카운팅값 중에서 더 작은 값을 넣는 것으로 변경

 

4.  위의 과정을 거치며 change_count 값을 최종값으로 출력했더니 8x8에 맞는 입력이 들어오는 경우에만 출력값이 제대로 나오고(예제 1,3,6) 10x13 등 8보다 큰 수의 입력이 들어오면 최소값을 출력하지 못 함(예제 2,4,5,7)

-> start_of_i 와 start_of_j 가 변하며 생기는 추가적인 값을 받지 못한다고 판단함

-> min_change 라는 2차원 배열을 새로 만들고, 여기에 (start_of_i , start_of_j)에 의한 각각의 8x8 보드에서의 최소값을 넣는 것으로 변경

-> 이후에 가장 마지막 이중 for 문에서 min_change 에 들어있는 값 중에서도 가장 작은 값을 result에 넣는 것으로 변경

-> 가장 마지막에는 result 값을 출력

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

char white_start [8][8] = 
{	
	{"WBWBWBWB"},
	{"BWBWBWBW"},
	{"WBWBWBWB"},
	{"BWBWBWBW"},
	{"WBWBWBWB"},
	{"BWBWBWBW"},
	{"WBWBWBWB"},
	{"BWBWBWBW"}
};

char black_start[8][8] =
{	
	{"BWBWBWBW"},
	{"WBWBWBWB"},
	{"BWBWBWBW"},
	{"WBWBWBWB"},
	{"BWBWBWBW"},
	{"WBWBWBWB"},
	{"BWBWBWBW"},
	{"WBWBWBWB"}
};

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	char board[50][50];

	int i, j;
	int start_of_i, start_of_j;
	int change_to_W = 0;
	int change_to_B = 0;
	int change_count = 0;
	int min_change[50][50] = { 0 };
	int result = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf(" %c", &board[i][j]);
		}
	}

	for (start_of_i = 0; start_of_i < n - 7; start_of_i++)
	{
		for (start_of_j = 0; start_of_j < m - 7; start_of_j++)
		{
			change_to_B = 0;
			change_to_W = 0;
			change_count = 0;

			for (i = start_of_i; i < start_of_i + 8; i++)
			{
				for (j = start_of_j; j < start_of_j + 8; j++)
				{
					
					if (board[i][j] != black_start[i-start_of_i][j-start_of_j])
					{
						change_to_W++;
					}
					if (board[i][j] != white_start[i-start_of_i][j-start_of_j])
					{
						change_to_B++;
					}
				}
			}

			if (change_to_W >= change_to_B)
			{
				change_count = change_to_B;
			}

			else
			{
				change_count = change_to_W;
			}

			min_change[start_of_i][start_of_j] = change_count;
		}
	}

	result = min_change[0][0];
	for (start_of_i = 0; start_of_i < n - 7; start_of_i++)
	{
		for (start_of_j = 0; start_of_j < m - 7; start_of_j++)
		{
			if (result > min_change[start_of_i][start_of_j])
			{
				result = min_change[start_of_i][start_of_j];
			}
		}
	}
	
	printf("%d", result);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ