취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23058번 문제인 뒤집기 게임이다.
문제는 아래 링크를 확인하자.

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

N이 8 이하이므로, 줄을 뒤집을 수 있는 경우의 수는 2^16 = 65536이고, 검은 돌과 흰 돌을 한번에 센다면 줄을 N번 넘게 뒤집을 필요가 없다는 점을 고려하면, "줄 뒤집기를 먼저 하고, 돌 하나씩을 뒤집는" 경우의 수들을 전부 탐색하는 것으로 문제를 해결할 수 있다는 것을 알 수 있다.

돌 뒤집기는 xor 연산을 이용하면 간단히 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int arr[8][8];

int mx = 100;

void func(int idx, int cnt) {
	if (cnt == N || idx == 2 * N) {
		int w = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				w += arr[r][c];
			}
		}
		mx = min(mx, cnt + min(w, N * N - w));
		return;
	}

	func(idx + 1, cnt);
	if (idx < N) {
		for (int r = 0; r < N; r++) {
			arr[r][idx] ^= 1;
		}
		func(idx + 1, cnt + 1);
		for (int r = 0; r < N; r++) {
			arr[r][idx] ^= 1;
		}
	}
	else {
		for (int c = 0; c < N; c++) {
			arr[idx - N][c] ^= 1;
		}
		func(idx + 1, cnt + 1);
		for (int c = 0; c < N; c++) {
			arr[idx - N][c] ^= 1;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> arr[r][c];
		}
	}

	func(0, 0);

	cout << mx;
}