[백준 BOJ] 1018번 체스판 다시 칠하기 (C++/cpp)

문제 설명

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

1018번: 체스판 다시 칠하기

 

접근 방법 - 브루트포스 알고리즘을 이용한 연산 문제

백준의 1018번 문제는 브루트포스 알고리즘을 이용하여 해결해야 하는 문제이다.

해당 문제는, 입력받은 보드를 잘라 체스판으로 만들 때 다시 칠해야하는 칸의 최소 개수를 구해야하는 문제이다.

브루트포스 알고리즘에 관한 다른 문제에 관해 이전에 필자가 작성한 글이 있다.

이 알고리즘에 대해 아직 어색하다면 아래의 링크 글을 한번 참고해보길 바란다.

https://smary-it.tistory.com/49

[백준 BOJ] 2798번 블랙잭 (Java)

이 문제 또한 위 링크의 문제처럼, 브루트포스 알고리즘을 이용했기 때문에 코드의 가독성이 떨어질 수 있다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력받을 보드의 정보를 저장할 2차원 배열(chess)을 전역 변수로 선언한다.

 

2) 입력받을 정보(보드의 가로 및 세로, 각 칸의 색깔)를 순차적으로 받는다.

 

3) 다시 색칠해야 하는 칸의 최솟값을 저장할 변수 min을 64로 초기화하며 선언한다.

(체스판의 크기인 64로 초기화하여, 연산에 차질이 없게끔 하였다.)

 

4) 보드의 각 칸을 탐색하는데, 잘릴 체스판의 크기를 고려하면서 탐색하도록 한다. 한 칸씩 탐색할 때마다 아래의 연산을 취하도록 한다.

- 해당 체스판에 대해, 다시 칠해야하는 칸의 개수를 저장할 변수 num을 0으로 초기화하며 선언한다.

- 해당 반복문에서 탐색된 칸을 ch에 저장해둔다.

- 다른 이중 반복문을 만들어서, ch를 이용해, 생성된 체스판에 대한 num의 값을 연산한다.

(하얀색 칸과 검은색 칸이 번갈아가며 배치되어있다는 점을 이용하여 연산을 진행한다.)

- 최종적으로 연산이 완료된 num이 min의 값보다 더 작을 때, min에 num의 값을 넣는다.

(이때, 체스판의 크기가 64이기 때문에 num의 값은 32를 넘을 수 없다. 따라서 그런 경우에는 64에 num의 값을 빼서 값을 조정하도록 한다.)

 

5) 연산이 완료된 min의 값을 출력한 뒤, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
using namespace std;

//백준 1018번 코드
char chess[50][50];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> chess[i][j];
		}
	}

	int min = 64;
	for (int i = 0; i < m - 7; i++) {
		for (int j = 0; j < n - 7; j++) {
			int num = 0;	//각 경우의 수 측정
			char ch = chess[i][j]; //특정 체스판의 첫번째 칸
			for (int k = i; k < i + 8; k++) {
				if ((k - i) % 2 == 0) {	//특정 체스판에 있어 짝수 행이라면
					for (int l = j; l < j + 8; l++) {
						if (k == i && l == j) { continue; }
						if (chess[k][l] == ch) {
							num++;
							if (chess[k][l] == 'B') { ch = 'W'; }
							else { ch = 'B'; }
							continue;
						}
						ch = chess[k][l];
					}
				}
				else {	//특정 체스판에 있어 홀수 행이라면
					for (int l = j + 7; l >= j; l--) {
						if (chess[k][l] == ch) {
							num++;
							if (chess[k][l] == 'B') { ch = 'W'; }
							else { ch = 'B'; }
							continue;
						}
						ch = chess[k][l];
					}
				}
			}
			if (num > 31) { num = 64 - num; }
			if (min > num) { min = num; }
		}
	}
	cout << min << endl;
}

 

제출 결과

(2022.02.22 백준 1018번 문제 제출 결과)