동전 뒤집기

[Gold I] 동전 뒤집기 - 1285

문제 링크

성능 요약

메모리: 2020 KB, 시간: 304 ms

분류

비트마스킹, 브루트포스 알고리즘, 그리디 알고리즘

제출 일자

2024년 7월 9일 17:57:12

문제 설명

N²개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.

<그림 1>

이들 N²개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.

<그림 2>	<그림 3>

<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.

N²개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.

출력

첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.

---

먼저 H : 0, T: 1 로 encoding 하면, 남은 것은 잘 뒤집는 작업을 수행한 뒤에 ‘1’ 비트를 최소한 하는 경우를 찾으면 된다.

여기서 중요한 발상은

행을 뒤집는 작업을 수행하면, 열에 대해서는 최적해가 이미 존재하기 떄문에 min 연산으로 비교적 쉽게 진행할 수 있다는 점이다.

(처음에 T의 개수가 N/2 이상이면 행,열 모두 뒤집는 로직을 구현하였는데 여기서 무한재귀 호출이 발생하여 Stack Overflowr가 되었다.)

따라서 DFS로 행을 뒤집고, 마지막에 열을 뒤집는 경우를 고려하면 끝.

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

int ret;
int N;


int countTails(const vector<int> &array){
    int sum=0;
    for(int j=0;j<N;j++){
        int n=0;
        for(int i=0;i<N;i++){
            if(array[i]&(1<<j)) n++;
        }
        sum+=min(n,N-n);
    }
    return sum;
}


void flipArray(vector<int> array,int targetRowIdx){
    // base case
    if(targetRowIdx==N) {
        ret=min(ret,countTails(array));
        return;
    }
  
    flipArray(array,targetRowIdx+1);
    // array[targetRowIdx]의 0~(N-1) 비트를 반전
    array[targetRowIdx]^=(1<<N)-1;
    flipArray(array,targetRowIdx+1);
}




int main() {

    cin>>N;
    ret=N*N;
    vector<int> array(N,0);
    // 초기화
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            char tmp;
            cin>>tmp;
            //tmp가 T면 array[i]의 j번째 비트를 1로 설정
            if(tmp=='T') {
                array[i]|=(1<<j);
            }
        }
    }
    //DFS
    flipArray(array,0);
    cout<<ret;
    return 0;
}