전구 끄기( BOJ 14927 )

문제 : https://www.acmicpc.net/problem/14927

14927번: 전구 끄기

 

문제 파악하기

불 켜진 전구를 효율적으로 끄는 방법을 찾는 문제입니다. 전구를 끄는 문제는 전통적으로 주변 전구들이 함께 영향을 받았는데 이번 문제 역시 하나의 전구를 작동시키면 주변 4방향(동서남북)의 전구 또한 영향을 받는 문제입니다. 이 문제를 해결하기 위해서는 전체적인 전구 상태를 보기 보다는 한 줄씩 나눠서 전구들을 확인해야 합니다.

 

문제 해결하기

우선, 전구는 항상 1번만 누르면 충분합니다. 2번 이상 누르는 건 비효율적이라는 건 누구나 알고 있습니다. 또한, 누르는 순서는 크게 상관없다는 걸 기억해야 합니다. 어떤 전구를 눌렀는지가 중요하지, 어떤 순서로 전구를 눌렀는지는 중요하지 않습니다. 그렇다면 우리는 문제를 쉽게 접근하기 위해 다음 규칙을 정해보겠습니다.

 

전구는 항상 맨 위에서부터 아래 순서로 누르기

 

그럼 이제 남은 건 어떤 전구를 누를 지 정하면 됩니다. 어떤 전구를 누를지 정하는 건 그리 어렵지 않습니다. 우리는 항상 위에서 아래로 전구를 누른다고 했습니다. 그리고 모든 전구가 꺼져있기 위해서는 항상 켜져있는 전구 밑에 위치한 전구를 눌러야 합니다. 예를 들어 i번째 줄과 (i+1)번째 줄에 전구가 다음과 같이 켜져있고, 현재 (i+1)번째 줄의 전구를 끌 차례라고 가정해봅시다.

 

O X X X X O O

X X X X O X O

 

이 상태에서 우리는 (i+1)번째 줄의 어떤 전구를 눌러야 할까요? 그건 바로, 첫 번째와 여섯 번째, 그리고 일곱 번째 전구를 눌러야 합니다. i번째 줄의 전구 중 켜져있는 전구를 끌 수 있는 방법은 위의 3개의 전구를 모두 누르는 방법밖에 없습니다. 이렇듯 우리는 이전 줄의 전구 상태를 확인하여 눌러야 하는 전구를 찾아낼 수 있습니다. 그리고 이렇게 모든 줄을 확인한 다음, 현재 불이 다 켜졌는지 꺼졌는지 확인하여 만약 불이 다 꺼졌으면 횟수를 비교하여 최소 횟수를 구할 수 있습니다.

 

여기서 문제가 끝날까요? 사실 우리는 한 가지 중요한 사실을 빼먹었습니다. 바로, 첫 번째 줄의 상태, 즉 시작 상태를 정하지 않았습니다. 우리는 첫 번째 줄을 어떻게 누르는지에 따라 위에서 설명한 방식으로 전구를 누르는 횟수를 구할 수 있습니다. 그러면 첫 번째 줄의 전구 중 어떤 전구를 눌러야 할까요? 그건 알 수 없습니다. 그렇기에 모든 경우의 수를 탐색해야 합니다. 첫 번째 줄을 누를 수 있는 모든 경우의 수(2^N)가지 경우에 대해 각각의 경우에 불을 끌 수 있는지 여부와 불을 끄게 되었을 때의 횟수를 모두 찾으면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 20
#define INF 0x7FFFFFFF
using namespace std;
 
int N, t, val;
vector< int > inp, init[2];
 
int ret;
int di[4]={-1,0,1,0}, dj[4]={0,-1,0,1};
 
 
bool safe(int x, int y) {
    if(x<0 or y<0 or x>=N or y>=N) return 0;
    else return 1;
}
 
void sv(int idx, int up, int cur, int cnt) {
    int push=0;
    int maps[3][NMAX]={0,};
 
    // 탐색 종료
    if(idx == N) {
        if(up == 0) ret = min( ret, cnt );
        return;
    }
 
    // 비트값 배열로 변환
    int nxt = inp[idx+1];
    for(int j=0;j<N;j++) {
        maps[0][j] = up & 1;
        maps[1][j] = cur & 1;
        maps[2][j] = nxt & 1;
 
        up/=2; cur/=2; nxt/=2;
    }
 
    // up값을 기준으로 불 켜기(up이 켜져있는 경우, cur누르기)
    for(int j=0;j<N;j++) {
        if(!maps[0][j]) continue;
 
        push++;
        maps[1][j] = 1-maps[1][j];
        for(int k=0;k<4;k++) {
            int ii = 1+di[k];
            int jj = j+dj[k];
 
            if(safe(ii, jj)) maps[ii][jj] = 1-maps[ii][jj];
        }
    }
 
    // 배열값을 비트값으로 변환하기
    for(int j=0;j<N;j++) {
        up += (maps[1][j]<<j);
        cur += (maps[2][j]<<j);
    }
 
    // 다음 상태로 보내기
    sv(idx+1, up, cur, cnt+push);
}
 
 
int main() {
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        val = 0;
        for(int j=0;j<N;j++) {
            scanf("%d", &t);
 
            val += (t<<j);
            if(i < 2) init[i].push_back(t);
        }
 
        inp.push_back(val);
    }
 
    // 시작 설정
    ret = INF;
    for(int tmp=0;tmp<(1<<N);tmp++) {
        int s;
        vector< int > bit[2];
 
        // init
        s = 0;
        bit[0] = init[0]; bit[1] = init[1];
 
        // tmp 비트에 맞춰 불 누르기
        for(int j=0;j<N;j++) {
            if(!(tmp & (1<<j))) continue;
 
            s++;
            bit[0][j] = 1-bit[0][j];
 
            for(int k=1;k<4;k++) {
                int ii, jj;
                ii = di[k]; jj = j+dj[k];
 
                if(safe(ii, jj)) bit[ii][jj] = 1-bit[ii][jj];
            }
        }
 
        // 배열을 비트로 변환
        int top, cur;
        top = cur = 0;
        for(int j=0;j<N;j++) {
            if(bit[0][j]) top += (1<<j);
            if(bit[1][j]) cur += (1<<j);
        }
 
        // 탐색
        sv(1, top, cur, s);
    }
    
    // 출력
    if(ret == INF) printf("-1");
    else printf("%d", ret);
}

후기

참신한 브루트포스 문제라고 생각합니다. 문제를 적절하게 추상화하여 함수를 구현해야 문제를 풀 수 있습니다. 다만, 비슷한 유형의 문제(https://www.acmicpc.net/problem/14939)를 풀어보면 쉽게 풀 수 있습니다. 저에게는 쉽지 않은 문제였습니다.