백준 1018 - 체스판 다시 칠하기

C++

1018 번 - 체스판 다시 칠하기

문제

스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다. 문제 출처

접근 방법

시간 복잡도를 생각하지 않고 무식하다면 무식한 방법으로 풀었다. 맨 왼쪽 위 칸이 흰색(W)과 검은색(B)인 완성 되어 있는 체스판을 만들어 놓는다. 이후 주어진 N X M 의 체스판에 (0,0) 부터 위의 틀을 하나씩 비교하여 다른 점의 개수를 센다.

이후 다른 부분이 가장 적은 위치를 찾고, 다른 점의 개수를 저장한다.

구현

W 와 B로 시작하는 체스판 틀을 만들기 위해, 중복 되는 두 줄 w_col, b_col 을 먼저 선언 한 뒤, boolean를 이용하여 번갈아 저장한다. 따라서 W로 시작하는 체스판 틀 b_frame , w_frame를 만든다.

SelChess()

이 틀을 전체 체스 판 위에 (0,0)을 왼쪽 위로 맞추어 하나씩 비교해 본다. (0,0) ~ (n-8, m-8) 까지 비교하면 전체 체스판 위 틀을 비교해 볼 수 있다.

ChkChess()

이후 W로 시작하는 틀, B로 시작하는 틀과 자른 체스판을 비교한다. idx_x와 idx_y는 for문의 i와 j가 자른 체스판 시작점을 나타내므로, 다른 변수를 이용하여 체스판 틀을 나타나게 하였다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
char graph[50][50];
char b_frame[8][8];
char w_frame[8][8];
int result = 999;

void SelChess();
void ChkChess(int y, int x);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	cin >> m;
	char* inputstr = new char[m];
	for (int i = 0; i < n; i++) {
		cin >> inputstr;
		for (int j = 0; j < m; j++) {
			graph[i][j] = inputstr[j];
		}
	}

	//W와 B로 시작하는 체스 판 틀을 만든다.
	char w_col[8] = { 'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B' };
	char b_col[8] = { 'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W' };
	bool tempbl = true;
	for (int i = 0; i < 8; i++) {
		if (tempbl) {
			for (int j = 0; j < 8; j++) {
				w_frame[i][j] = w_col[j];
				b_frame[i][j] = b_col[j];
			}
			tempbl = !tempbl;
		}
		else {
			for (int j = 0; j < 8; j++) {
				w_frame[i][j] = b_col[j];
				b_frame[i][j] = w_col[j];
			}
			tempbl = !tempbl;
		}
	}
	SelChess();
	cout << result;
	return 0;
}
//체스 판 틀을 놓을 자리를 고른다. 10*12 크기의 판이면, 8*8이 (0,0) 부터 (2,4)까지 이동하며 비교한다.
void SelChess() {
	for (int i = 0; i <= (n - 8); i++) {
		for (int j = 0; j <= (m - 8); j++) {
			ChkChess(i, j);
		}
	}
}

//자른 체스판과 'B', 'W'으로 시작하는 체스판 틀을 비교하여 다른 부분을 찾는다.
void ChkChess(int y, int x) {
	int first_b = 0;
	int first_w = 0;
	int idx_y = 0;
	int idx_x = 0;
	for (int i = y; i < y + 8; i++) {
		for (int j = x; j < x + 8; j++) {
			if (graph[i][j] != w_frame[idx_y][idx_x]) {
				first_w++;
			}
			else if (graph[i][j] != b_frame[idx_y][idx_x]) {
				first_b++;
			}
			idx_x++;
		}
		idx_y++;
		idx_x = 0;
	}
	result = min(result, min(first_b, first_w));
}

후기 및 개선할 점

후기: 1시간 반 소요. 집중하면 1시간까지 줄일 수 있을건데..