[백준]불 끄기(14939)

문제 링크 : [백준]불 끄기(14939)

문제 설명

10 * 10의 크기의 배열에 불이 켜져있는지에 대한 정보가 주어집니다.
한 곳의 불을 켜거나 끄게 되면 그 위치와 함께 그 위치의 위, 아래, 왼쪽, 오른쪽까지 함께 불의 상태가 바뀝니다.(켜져있는 상태 -> 꺼짐, 꺼져있는 상태 -> 켜짐)
모든 불을 끄기 위해서는 최소 몇번 스위치를 눌려야 하는지 구하세요.

입력

S_ij(#은 꺼져있는 상태, O는 켜져있는 상태)

#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#

출력

4

카테고리

#브루트포스 #그리디

시간 복잡도 상한

O(2^N) 이상으로도 가능합니다.
O(N!) 정도만 아니면 될 것 같습니다.

해결 방법

1. 모든 스위치를 꺼보고 켜보고 해보면 답을 구할 수 있습니다.
2. 단, O(2^{N * N}), 즉, 2¹⁰⁰ 이라는 어마어마한 시간복잡도가 탄생합니다.
3. 조건을 단순화 시켜야합니다.
4. 각 스위치는 두번 이상 누를 필요가 없습니다.
   4-1. 두 번 스위치를 누르면 원래 상태로 돌아오기 때문에, 최소비용의 후보값으로는 절대 올 수 없으므로 무시해도 됩니다.
5. 스위치를 누르는 순서는 중요하지 않습니다.
   5-1. 스위치를 누르는 순서에 따라서 전체 상태값이 다르지 않습니다.
6. 4, 5를 가지고, 스위치를 누르는 방법을 단순화 시켜봅니다.
7. 개발자는 편의상 왼쪽 위에서 오른쪽 아래로 가는 것을 좋아합니다.(다른 순서대로해도 무관합니다. 여기서는 왼쪽 위를 기준으로 합니다.)
8. (i,j)의 불 상태를 꺼지게 하기 위해서는 최종적으로 (i+1,j)에서 스위치를 누르는지에 따라서 결정됩니다.
9. 따라서 (i+1,j)를 지나간다면, (i,j)의 상태는 절대로 바꿀 수 없습니다.
10. 즉 (i+1,j)의 상태는 (i,j)의 불이 켜져있다면 스위치를 누르고, 그렇지 않다면 스위치를 누르지 않아야 합니다.
11. 그렇다면 맨 윗줄은 어떻게 해야할까요??
12. 어쩔 수 없이 모든 경우에 대해서 다 해봐야 합니다.
13. 그래봐야 2¹⁰ = 1024가지 밖에 되지 않습니다.
14. 정리하자면, 맨 윗줄은 모든 경우의 수로 나열해보고, 그 상태에 따라서 아랫줄들을 8,9,10에 따라서 스위치를 누를지에 대한 판단을 하면 됩니다.
15. 마지막까지 모든 스위치를 다루고 난 후, 불이 하나라도 켜져있으면 -1을 return 합니다.

시간복잡도

O(2^N * N * N)

코드

#include<cstdio>
#include<algorithm>
#define N 10
using namespace std;
int i,j,a,x[N],q[N][N],o[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char t;
void c(int s[][N],int x,int y){
    s[x][y]^=1;
    for(int k=0;k<4;k++){
        int nx=x+o[k][0],ny=y+o[k][1];
        if(nx>=0&&ny>=0&&nx<N&&ny<N)s[nx][ny]^=1;
    }
}
int r(int p){
    if(p==N){
        int a=0;
        int s[N][N];
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)s[i][j]=q[i][j];
        for(int i=0;i<N;i++){
            if(x[i])a++,c(s,0,i);
        }
        for(int i=1;i<N;i++){
            for(int j=0;j<N;j++){
                if(s[i-1][j])a++,c(s,i,j);
            }
        }
        for(i=0;i<N;i++)for(j=0;j<N;j++)if(s[i][j])return -1;
        return a;
    }
    x[p]=0;
    int a1=r(p+1);
    x[p]=1;
    int a2=r(p+1);
    return a1<0?a2:a2<0?a1:min(a1,a2);
}
int main(){
    for(;i<N;i++)for(j=0;j<N;j++)scanf("\n%c",&t),q[i][j]=t=='O';
    printf("%d",r(0));
}