취미로 코딩하기

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

이번에 볼 문제는 백준 9079번 문제인 동전 게임이다.
문제는 아래 링크를 확인하자.

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

같은 뒤집을 수 있는 방법을 2회 시행하는 것은 그 시행을 하지 않는 것과 같으므로, 각 뒤집을 수 있는 방법에 대하여 2회 이상 뒤집는 경우는 고려할 필요가 없음을 관찰하자. 즉, 문제의 답이 될 가능성이 있는 있는 시행은 가능한 각 시행에 대하여 그 시행을 하거나 안 하거나의 $2^8$가지 경우로 좁힐 수 있다.

위의 각 경우를 완전탐색하여 문제를 해결하자. 글쓴이는 각 뒤집는 방법별로 뒤집게 되는 칸을 정리한 flips 배열을 아래와 같이 만들어 완전탐색을 구현하였다.

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

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

int T;
int ans, cnt;
pair<int, int> flips[8][3];
int board[3][3];

void func(int idx) {
	if (idx == 8) {
		int cur = board[0][0];
		bool chk = 1;
		for (int r = 0; r < 3; r++) {
			for (int c = 0; c < 3; c++) {
				if (board[r][c] ^ cur) chk = 0;
			}
		}

		if (chk) ans = min(ans, cnt);
	}
	else {
		func(idx + 1);
		for (int i = 0; i < 3; i++) {
			int r = flips[idx][i].first, c = flips[idx][i].second;
			board[r][c] ^= 1;
		}
		cnt++;
		func(idx + 1);
		cnt--;
		for (int i = 0; i < 3; i++) {
			int r = flips[idx][i].first, c = flips[idx][i].second;
			board[r][c] ^= 1;
		}
	}
}

void solve() {
	ans = 1000000007, cnt = 0;
	for (int r = 0; r < 3; r++) {
		for (int c = 0; c < 3; c++) {
			char tmp; cin >> tmp;
			if (tmp == 'H') board[r][c] = 0;
			else board[r][c] = 1;
		}
	}
	func(0);

	if (ans > 1000000000) cout << -1 << '\n';
	else cout << ans << '\n';
}

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

	flips[0][0] = { 0,0 }, flips[0][1] = { 0,1 }, flips[0][2] = { 0,2 };
	flips[1][0] = { 1,0 }, flips[1][1] = { 1,1 }, flips[1][2] = { 1,2 };
	flips[2][0] = { 2,0 }, flips[2][1] = { 2,1 }, flips[2][2] = { 2,2 };
	flips[3][0] = { 0,0 }, flips[3][1] = { 1,0 }, flips[3][2] = { 2,0 };
	flips[4][0] = { 0,1 }, flips[4][1] = { 1,1 }, flips[4][2] = { 2,1 };
	flips[5][0] = { 0,2 }, flips[5][1] = { 1,2 }, flips[5][2] = { 2,2 };
	flips[6][0] = { 0,0 }, flips[6][1] = { 1,1 }, flips[6][2] = { 2,2 };
	flips[7][0] = { 2,0 }, flips[7][1] = { 1,1 }, flips[7][2] = { 0,2 };

	cin >> T;
	while (T--) solve();
}