[Baekjoon/백준][1018][C/C++] 체스판 다시 칠하기

728x90

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

브루트포스 알고리즘. 모든 경우의 수를 따져가며 풀어야 하므로, 문제를 디테일하게 점검하여 문제의 요구조건을 놓치지 않도록 해야 한다.

1. 문제

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

[문제]

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

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

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

[입력]

[출력]

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

[예제 입력 1]

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

[예제 출력 1]

[예제 입력 2]

10 13
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
BBBBBBBBWBWBW
BBBBBBBBBWBWB
WWWWWWWWWWBWB
WWWWWWWWWWBWB

[예제 출력 2]

[예제 입력 3]

8 8
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB

[예제 출력 3]

[예제 입력 4]

9 23
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBB
BBBBBBBBBBBBBBBBBBBBBBW

[예제 출력 4]

[예제 입력 5]

10 10
BBBBBBBBBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBWBWBWBWB
BWBWBWBWBB
BBBBBBBBBB

[예제 출력 5]

[예제 입력 6]

8 8
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWWWB
BWBWBWBW

[예제 출력 6]

[예제 입력 7]

11 12
BWWBWWBWWBWW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW
BWWBWBWWWBWW
WBWWBWBBWWBW
BWWBWBBWWBWW
WBWWBWBBWWBW

[예제 출력 7]

2. 풀이

풀이를 시작하기 전에

fgets 함수를 이용하여 문제를 풀었다. 다만, fgets함수는 자신만의 독특한 특징이 있어, 이 부분을 짚고 넘어가야 함수를 이용할 때 헤매지 않는다. fgets 함수의 특징은 다음과 같다. (링크를 참조하거나, 아래쪽 글을 읽자.)

https://lumir.tistory.com/31

[C][header][stdio.h] fgets

fgets #include // C++ 의 경우 char* fgets(char* str, int num, FILE* stream); 특징 1. 개행(=newline)(='\n') 혹은 파일끝(=EOF)을 만날 때 까지, 해당 stream의 buffer에서 문자열을 읽어들인다. (개행(=newline)(='\n') 혹은 파

lumir.tistory.com

fgets 함수의 특징

1. 개행(=newline)(='\n') 혹은 파일끝(=EOF)을 만날 때까지, 해당 stream의 buffer에서 문자열을 읽어 들인다.

(개행(=newline)(='\n') 혹은 파일끝(=EOF)을 만나면, 입력이 종료된다.)

2. 문자열을 읽어 들인 후, 문자열 끝에 NULL(='\0')값이 자동으로 추가된다.

3. fgets는 gets와 달리, 개행(=newline)(='\n')이 포함된 채 저장된다.

문제풀이

/* Input */

문제의 입력값인 N과 M을 입력받는다. 이때, N과 M을 입력받은 후 필연적으로 '\n'(=개행)(=Newline)이 입력되므로, 입력버퍼에는 '\n'이 존재하게 된다. ∴ getchar함수의 호출을 통해 '\n'을 입력버퍼에서 지워주어야 한다.

/* 2차원 배열 동적할당 */

C언어에서 2차원 배열을 동적할당하는 방법은 아래 코드와 같다.

이때, '\n'과 '\0'문자가 들어올 것을 대비하여 가로의 길이를 M+2로 선언한다.

/* Input */

fgets 함수를 통해 W와 B로 구성된 문자열을 입력받는다.

/* 체스판 체크 */

문제의 핵심 파트. 코드가 긴 Version과 간략한 Version 2가지를 기술해 두었다. (아래 코드를 참고하자.)

핵심아이디어는 다음과 같다. 체스판의 모양(패턴)은 다음의 2가지 경우만 존재한다.

[① 색깔이 W로 시작하는 경우(W_start)]

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

[② 색깔이 B로 시작하는 경우(B_start)]

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

BWBWBWBW

WBWBWBWB

∴ 입력받은 체스판을 8x8의 크기로 자른 후, 위 패턴과 다른 부분의 개수를 각각 계산한 다음(W_start인 경우와 B_start인 경우), 둘 중 최솟값을 구하면 된다.

/* 출력 */

입력받은 체스판을 8x8의 크기로 자른 모든 경우의 수에 대해 각각의 최솟값을 구한 후, 각각의 최솟값들에 대해 최솟값을 구해 출력하면 된다. (여기에 해당하는 값이 min_num 이다.)

3. 코드

#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 최댓값, 최솟값 정의.

#define min(a,b) (((a) > (b)) ? (b) : (a))

int main(int argc, char* argv[]) {
	/* Input */
	int N, M; scanf("%d %d", &N, &M); //N은 세로, M은 가로.
	getchar(); //'\n'을 입력버퍼에서 지움.

	/* 2차원 배열 동적할당 */
	char** arr = (char**)calloc(N, sizeof(char*));
	for (int i = 0; i < N; i++)
		arr[i] = (char*)calloc(M+2, sizeof(char)); //'\n'과 '\0' 고려.

	/* Input */
	for (int i = 0; i < N; i++)
		fgets(arr[i], (M + 2) * sizeof(char), stdin);
		//sizeof(arr[i])를 하면, arr[i] = int형 싱글 포인터 크기인 8이 반환된다.
		
	/* 체스판 체크 */
	int min_num = INT_MAX;

	for (int col = 0; col <= N - 8; col++) {
		for (int row = 0; row <= M - 8; row++) {
			int W_start = 0, B_start = 0;

			/* 8 x 8 크기의 체스판 체크 */
			for (int i = col; i < col + 8; i++) {
				for (int j = row; j < row + 8; j++) {

					/* 세로 인덱스 짝수 */
					if (i % 2 == 0) {
						/* 가로 인덱스 짝수 */
						if (j % 2 == 0) {
							if (arr[i][j] != 'W') W_start++;
							if (arr[i][j] != 'B') B_start++;
						}
						/* 가로 인덱스 홀수 */
						else if (j % 2 == 1) {
							if (arr[i][j] != 'B') W_start++;
							if (arr[i][j] != 'W') B_start++;
						}
					}

					/* 세로 인덱스 홀수 */
					else if (i % 2 == 1) {
						/* 가로 인덱스 짝수 */
						if (j % 2 == 0) {
							if (arr[i][j] != 'B') W_start++;
							if (arr[i][j] != 'W') B_start++;
						}
						/* 가로 인덱스 홀수 */
						else if (j % 2 == 1) {
							if (arr[i][j] != 'W') W_start++;
							if (arr[i][j] != 'B') B_start++;
						}
					}
				}
			}

			min_num = min(min_num, min(W_start, B_start));
		}
	}

	/* 출력 */
	printf("%d", min_num);

	/* 마무리 */
	for (int i = 0; i < N; i++)
		free(arr[i]);
	free(arr);

	return 0;
}

/* '8 x 8 크기의 체스판 체크' 파트 간략화 Ver. */
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 최댓값, 최솟값 정의.

#define min(a,b) (((a) > (b)) ? (b) : (a))

int main(int argc, char* argv[]) {
	/* Input */
	int N, M; scanf("%d %d", &N, &M); //N은 세로, M은 가로.
	getchar(); //'\n'을 입력버퍼에서 지움.

	/* 2차원 배열 동적할당 */
	char** arr = (char**)calloc(N, sizeof(char*));
	for (int i = 0; i < N; i++)
		arr[i] = (char*)calloc(M + 2, sizeof(char)); //'\n'과 '\0' 고려.

	/* Input */
	for (int i = 0; i < N; i++)
		fgets(arr[i], (M + 2) * sizeof(char), stdin);
	//sizeof(arr[i])를 하면, arr[i] = int형 싱글 포인터 크기인 8이 반환된다.

	/* 체스판 체크 */
	int min_num = INT_MAX;

	for (int col = 0; col <= N - 8; col++) {
		for (int row = 0; row <= M - 8; row++) {
			int W_start = 0, B_start = 0;

			/* 8 x 8 크기의 체스판 체크 */
			for (int i = col; i < col + 8; i++) {
				for (int j = row; j < row + 8; j++) {
					/* 세로+가로 인덱스 짝수 */
					if ((i + j) % 2 == 0) {
						if (arr[i][j] != 'W') W_start++;
						if (arr[i][j] != 'B') B_start++;

					}

					/* 세로+가로 인덱스 홀수 */
					else if ((i + j) % 2 == 1) {
						if (arr[i][j] != 'B') W_start++;
						if (arr[i][j] != 'W') B_start++;
					}
				}
			}

			min_num = min(min_num, min(W_start, B_start));
		}
	}

	/* 출력 */
	printf("%d", min_num);

	/* 마무리 */
	for (int i = 0; i < N; i++)
		free(arr[i]);
	free(arr);

	return 0;
}

728x90

저작자표시 비영리 변경금지

'「⌨️ᴄs」PS > 백준_브루트포스' 카테고리의 다른 글

[Baekjoon/백준][2798][C/C++] 블랙잭 (0)	2023.01.30
[Baekjoon/백준][4673][C/C++] 셀프 넘버 (0)	2023.01.18

𝕃𝕦𝕄𝕚𝕣

[Baekjoon/백준][1018][C/C++] 체스판 다시 칠하기

0. 개요

1. 문제

[문제]

[입력]

[출력]

[예제 입력 1]

[예제 출력 1]

[예제 입력 2]

[예제 출력 2]

[예제 입력 3]

[예제 출력 3]

[예제 입력 4]

[예제 출력 4]

[예제 입력 5]

[예제 출력 5]

[예제 입력 6]

[예제 출력 6]

[예제 입력 7]

[예제 출력 7]

2. 풀이

3. 코드

'「⌨️ᴄs」PS > 백준_브루트포스' 카테고리의 다른 글

티스토리툴바