BOJ 1285 동전 뒤집기

NxN 행렬로 동전이 앞 뒤로 놓여 있고 1번 연산에 행 또는 열 전체를 뒤집을 수 있다. 이때 뒷면이 위를 향하는 동전의 개수를 최소로 하는 연산의 수를 구하는 문제이다.

 

이 문제를 완전 탐색을 한다면 행을 바꿀때마다 열의 상태도 같이 변한다. 따라서 행을 바꾸는 경우의수 2^20, 열을 바꾸는 경우의수 2^20 총 2^40이 된다. 루트포스 알고리즘을 이용하여 완전 탐색을 한다면 시간 초과 발생

 

핵심은 우리의 목표는 T가 최소가 되도록 뒤집어야 한다. 만약에 어떤 상태를 미리 알 수 있다면 그 상태에서 어떤 행 또는 열을 뒤집을지 빠르게 판단할 수 있다.

 

여기서 어떤 상태를 미리 알기위해 비트마스킹 개념을 도입한다. 비트마스킹이란 n<20 이하 이면서 상태가 0또는1 인 집합을 하나의 비트로 표현하는 방식을 말한다.(자세한 개념은 따로 정리할 계획이다...)  

 

풀이 방법은 행을 기준으로 2^n개의 경우의 수를 모두 탐색한다. 예를들어 n=3 일때 행을 뒤집을수 있는 경우의 수는 8가지가 된다.

 

각각의 경우의 수에 대해 특정 행을 뒤집는 작업을 반복해야한다. 이때 뒤집는 방법은 두가지이다.

1. 비트마스크(000,001,010,011,100,101,110,111)로 표현하여 bit&(1<<i) == (1<<i) 즉 특정 비트마스크를 선택한 후 쉬프트 연산을 통해 나온 결과가 참이라면 i 번째 행을 뒤집어준다.

2. 각 행에대한 비트마스크 값을 미리 계산한 후 ~연산을 이용하여 뒤집어준다.

 

1번 풀이는 다음과 같다.

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

int n;

bool init_m[21][21];
bool m[21][21];

void rev(int isrow, int k) {
    if (isrow) {
        for (int i = 0; i < n; i++) m[k][i] = !m[k][i];
    } else {
        for (int i = 0; i < n; i++) m[i][k] = !m[i][k];
    }
}

void init() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) m[i][j] = init_m[i][j];
}

int main() {
    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < n; j++) {
            init_m[i][j] = s[j] == 'H' ? true : false;
            if (init_m[i][j]) ans++;
        }
    }
    int set = (1 << n) - 1;
    for (int subset = set;; subset = ((subset - 1) & set)) {
        init();
        int cmp = 0;
        for (int i = 0; i < n; i++) {
            int cur = 1 << i;
            if ((subset & cur) == cur) rev(0, i);
        }
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (!m[i][j]) cnt++;
            }
            if (cnt > n - cnt) {
                rev(1, i);
                cmp += n - cnt;
            } else {
                cmp += cnt;
            }
        }
        ans = min(ans, cmp);
        if (subset == 0) break;
    }

    cout << ans << "\n";
}

2번 풀이는 다음과 같다.

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

const int INF = 987654321;
int n, a[44], ret = INF;
string s;
void go(int here)
{
	if(here == n + 1)
	{
		int sum = 0;
		for(int i = 1; i <= (1 << (n - 1)); i *= 2)
		{
			int cnt = 0;
			for(int j = 1; j <= n; j++) if((a[j] & i)==i)cnt++;
			sum += min(cnt, n - cnt);
		}
		ret = min(ret, sum);
		return;
	}

	go(here + 1);
	a[here] = ~a[here];
	go(here + 1);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> s;
		int value = 1;
		for(int j = 0; j < s.size(); j++)
		{
			if(s[j] == 'T')a[i] |= value;
			value *= 2;
		}
	}
	go(1);
	cout << ret << "\n";
	return 0;
}

 

 

1 또는 2 번 방식을 이용하여 행을 뒤집었다면 이후 모든 열을 탐색하면서 열을 뒤집는게 좋은지 안뒤집는게 좋은지 판단한다. 판단하는 방법은 특정 열에 대해 min(T, N - T)를 누적하고 모든 열을 탐색하였을 때 최소인 값을 구하면 된다.