이번에는 백준 1285번 동전 뒤집기 문제를 풀어보았습니다.
처음에는 행과 열을 모두 뒤집는 경우를 완전탐색하려고 했습니다.
하지만 행과 열을 모두 고려하면 경우의 수가 최대 2^40이 되어 탐색이 불가능했습니다.
다시 생각해보니 행을 뒤집는 경우만 모두 탐색한 뒤, 열은 실제로 뒤집지 않더라도 현재 상태에서 최소 뒷면 개수를 바로 계산할 수 있다는 점을 이용하여 해결하였습니다.
이후 같은 로직을 비트마스킹으로 다시 구현해보았습니다.
문제 설명
각 행 또는 각 열을 선택하여 해당 줄의 모든 동전을 뒤집을 수 있습니다.
모든 작업이 끝났을 때 뒷면(T)의 개수가 최소가 되도록 해야 합니다.
최소가 되는 뒷면 개수를 구하는 문제입니다.
풀이 아이디어
V1
행을 뒤집는 모든 경우를 DFS로 탐색하였습니다.
행이 모두 결정된 이후에는 각 열을 확인하였습니다.
현재 열에 뒷면이 a개라면 열을 뒤집지 않는 경우는 a개, 뒤집는 경우는 N-a개가 됩니다.
따라서 각 열마다 min(a, N-a)를 더하면 해당 상태에서의 최소 뒷면 개수를 구할 수 있었습니다.
V2
V1과 동일한 로직이지만 bool 배열 대신 비트마스킹을 이용하여 구현하였습니다.
각 행을 하나의 정수로 저장한 뒤 비트 연산으로 각 열의 상태를 확인하였습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
bool bitmap[20][20];
int N;
int ret = INT_MAX;
int calculate() {
int cnt = 0;
for (int i = 0; i < N; i++) {
int t=0;
for (int j = 0; j < N; j++) {
if (bitmap[j][i]) t++;
}
cnt += min(t, N-t);
}
return cnt;
}
void flip(int row) {
for (int i = 0; i < N; i++) {
bitmap[row][i] = !bitmap[row][i];
}
}
void solve(int st) {
if (st == N) {
ret = min(ret, calculate());
return;
}
solve(st+1);
flip(st);
solve(st+1);
flip(st);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i=0; i<N; i++) {
string s;
cin >> s;
for (int j=0; j<N; j++) {
bitmap[i][j] = (s[j] == 'T');
}
}
solve(0);
cout << ret << '\n';
return 0;
}V1 풀이 흐름
- 입력을 받아 동전 상태를 저장합니다.
- DFS를 이용하여 각 행을 뒤집거나 뒤집지 않는 모든 경우를 탐색합니다.
- 모든 행이 결정되면 각 열의 뒷면 개수를 계산합니다.
- 열마다 뒤집는 경우와 뒤집지 않는 경우 중 작은 값을 선택합니다.
- 모든 열을 계산한 뒤 최솟값을 갱신합니다.
V1 구현 포인트
1. 행 뒤집기
현재 행의 모든 동전을 뒤집었습니다.
void flip(int row) {
for (int i = 0; i < N; i++) {
bitmap[row][i] = !bitmap[row][i];
}
}DFS에서는 행을 뒤집는 경우와 뒤집지 않는 경우를 모두 탐색하였습니다.
2. 열의 최소 뒷면 계산
모든 행이 결정되면 각 열의 뒷면 개수를 계산하였습니다.
int t = 0;
for (int j = 0; j < N; j++) {
if (bitmap[j][i]) t++;
}현재 열에 뒷면이 t개라면
- 뒤집지 않는 경우 :
t - 뒤집는 경우 :
N-t
이므로
cnt += min(t, N-t);를 이용하여 최소 개수를 계산하였습니다.
3. 행만 완전탐색
행만 완전탐색하면 모든 경우를 확인할 수 있습니다.
solve(st+1);
flip(st);
solve(st+1);
flip(st);각 행마다 뒤집는 경우와 뒤집지 않는 경우를 모두 탐색하도록 구현하였습니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int N;
int inp[21];
int ret = INT_MAX;
int calculate() {
int sum = 0;
for (int i=1; i<=(1 << (N-1)); i*=2) {
int cnt = 0;
for (int j=1; j<=N; j++) {
if (inp[j] & i) cnt++;
}
sum += min(cnt, N-cnt);
}
return sum;
}
void solve(int st) {
if (st == N+1) {
ret = min(ret, calculate());
return;
}
solve(st+1);
inp[st] = ~inp[st];
solve(st+1);
inp[st] = ~inp[st];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
string s;
cin >> s;
int tmp = 1;
for (int j=0; j<s.length(); j++) {
if (s[j] == 'T') inp[i] |= tmp;
tmp *= 2;
}
}
solve(1);
cout << ret << '\n';
return 0;
}V2 풀이 흐름
- 각 행을 하나의 비트로 저장합니다.
- DFS를 이용하여 행을 뒤집거나 뒤집지 않는 모든 경우를 탐색합니다.
- 모든 행이 결정되면 비트 연산으로 각 열의 뒷면 개수를 계산합니다.
- 열마다 최소 뒷면 개수를 더합니다.
- 최솟값을 갱신합니다.
V2 구현 포인트
1. 비트마스킹으로 행 저장
각 행을 하나의 정수로 저장하였습니다.
if (s[j] == 'T')
inp[i] |= tmp;비트가 1이면 뒷면(T)을 의미하도록 하였습니다.
2. 행 뒤집기
행을 뒤집을 때는 비트 NOT 연산을 이용하였습니다.
inp[st] = ~inp[st];별도의 반복문 없이 한 번에 뒤집을 수 있었습니다.
3. 비트 연산으로 열 확인
각 열의 상태를 비트 연산으로 확인하였습니다.
if (inp[j] & i)
cnt++;현재 열에서 뒷면의 개수를 계산하였습니다.
4. 열의 최소 뒷면 계산
V1과 동일하게 각 열에서 뒤집는 경우와 뒤집지 않는 경우 중 작은 값을 선택하였습니다.
sum += min(cnt, N-cnt);모든 열을 계산한 뒤 최소 뒷면 개수를 구하였습니다.
