[백준] 1640번: 동전 뒤집기

문제

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

설명

 N * M 크기로 동전을 배치한다. 앞면을 0, 뒷면을 1이라고 할 때, 행 또는 열에 있는 동전들을 뒤집어서 행과 열에 위치한 모든 동전의 뒷면(1)의 개수를 짝수로 바꾸는 최소 횟수를 구하는 문제이다. 처음에는 무슨 알고리즘을 써야 할지 감이 안 잡혔는데, 역시 애드 혹 문제였다.

코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int col[1001];
int row[1001];

// 1. 행 또는 열을 짝수 또는 홀수로 통일한다.
// 2. 홀수 개로 통일한 경우 다른 행 또는 열의 짝수 개를 뒤집는다.
// 3. 짝수 개로 통일한 경우 그 반대
int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;

		for (int j = 0; j < m; j++) {
			int x = s[j] - '0';
			row[i] += x;
			col[j] += x;
		}
	}

	int row_odd = 0, row_even = 0, col_odd = 0, col_even = 0;
	for (int i = 0; i < n; i++) {
		if (row[i] % 2)
			row_odd++;
		else
			row_even++;
	}
	for (int i = 0; i < m; i++) {
		if (col[i] % 2)
			col_odd++;
		else
			col_even++;
	}

	int ans1, ans2;

	// 행을 모두 짝수로
	if (row_odd % 2 == 0)
		ans1 = row_odd + col_odd;
	else
		ans1 = row_odd + col_even;

	// 행을 모두 홀수로
	if (row_even % 2 == 0)
		ans2 = row_even + col_odd;
	else
		ans2 = row_even + col_even;

	cout << min(ans1, ans2);

}

---

 문제의 예제 1이다. O는 행 또는 열에서 1의 개수가 홀수, E는 짝수라고 하자. 2행을 뒤집어보자.

 

 2행에서 1의 개수는 짝수였으나, 뒤집게 되면 홀수가 된다. 또한 모든 열의 홀수 또는 짝수 여부가 바뀌었다. 이것으로 알 수 있는 사실이 있다. 첫째, 행 또는 열을 뒤집으면 해당 행 또는 열의 홀수, 짝수 여부가 바뀐다. 0이 1이 되고 1이 0이 되므로 조금만 생각하면 당연한 사실이라는 것을 알 수 있다. 둘째, 만약 행을 뒤집었다면 모든 열의 홀짝 여부가 바뀐다. 열을 뒤집었다면 모든 행의 홀짝 여부가 바뀐다. 이 또한 조금만 생각하면 당연하다는 것을 알 수 있다.

 그렇다면 과연 모든 행과 열의 1의 개수를 짝수로 만들기 위해서 어떻게 해야 할까? 모든 행을 짝수로 만든 후 열을 짝수로 만드는 방법이 있다. 또는 모든 행을 홀수로 만든 후 열을 짝수로 만드는 방법이 있다. 문제의 목표가 모든 행과 열을 짝수로 만드는 것인데 왜 홀수로 만드냐고 하면, 홀수인 행 또는 열만 뒤집는 것이 정해가 아니다. 반례가 예제 1이다. 예제 1은 짝수인 2행과 2열을 뒤집는 것이 최적이다. 어쨌든 경우의 수는 크게 두 가지인 것이다. 참고로 모든 행을 짝수 또는 홀수로 통일하든 모든 열을 짝수 또는 홀수로 통일하든 상관없다. 나는 행을 통일시켰다.

 행을 짝수 또는 홀수로 통일하면, 열에 대해서만 짝수로 맞춰주기면 하면 된다. 그렇다면 어떤 열을 뒤집어야 하는가? 무조건 홀수인 열을 뒤집으면 안 된다. 이전 그림에서, 행 하나를 뒤집으면 모든 열의 홀짝 여부가 바뀌었다. 만약 두 개의 행을 뒤집으면 어떻게 될까? 열의 홀짝 여부는 그대로 유지될 것이다. 즉, 만약 홀수 개의 행을 뒤집어 홀짝을 맞췄다면 처음에 짝수였던 열을 뒤집어야 되는 것이다. 만약 짝수 개의 행을 뒤집었다면 처음에 홀수였던 열을 뒤집어야 한다. 즉, 각각의 경우의 수에서 추가로 두 가지 경우의 수가 생긴 것이다.