백준 문제 14927번 전구 끄기 문제풀이 c++

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

14927번: 전구 끄기

 

문제해석

 

N이 최대 18개이라 그냥 브루트 포스를 하면 2^324번 해야해서 당연히 아닐거고.. 어떻게 해야하나 고민하다 모르겠어서 구글링해서 찾아보았다.

 

찾아본결과 그리디로 풀수있는 문제였다.

 

브루트포스를 맨 윗줄 하나에 대해서만 수행한 후 아랫줄로 내려가서 윗 전구가 켜져있으면 윗 전구를 꺼주는 것을 마지막 라인까지 하면 되는것이다.

 

그 후 모든 전구가 꺼져있다면 이전 최소값과 비교하여 더 작은것으로 업데이트해주는것이다.

 

어떻게 이것이 최적해를 어떻게 보장해주는지 증명을 어떻게해야하나 너무 어려운거같다.

 

아무튼 위 방식대로하면 맨윗줄만 모든 경우를 하니까 2^18가지의 경우밖에없어서 시간초과가 안나고 아래와 같이 코드를 작성하였다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void setting();
void copy();
void dfs(int index,int size,int depth);
bool check();
bool inside(int ny,int nx);
vector <int> v;
bool visited[18];
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
bool base[18][18];
bool a[18][18];
int N;
int ans=9999;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    setting();
    for(int i=0; i<=N; i++)
    {
        dfs(0,i,0);
    }
    if(ans==9999)
    {
        cout<<-1;
    }
    else
    {
        cout<<ans;
    }
}
void setting(){
    cin>>N;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin>>base[i][j];
        }
    }
}
void copy(){
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            a[i][j]=base[i][j];
        }
    }
}
void dfs(int index,int size,int depth){
    if(depth==size)
    {
        copy();
        int ny;
        int nx;
        int cnt=0;
        for(int i=0; i<v.size(); i++)
        {
            a[0][v[i]]=!a[0][v[i]];
            cnt++;
            for(int j=0; j<4; j++)
            {
                ny=dy[j];
                nx=v[i]+dx[j];
                if(inside(ny,nx))
                {
                    a[ny][nx]=!a[ny][nx];
                }
            }
        }
        
        for(int i=1; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                if(a[i-1][j]==1)
                {
                    a[i][j]=!a[i][j];
                    cnt++;
                    for(int k=0; k<4; k++)
                    {
                        ny=i+dy[k];
                        nx=j+dx[k];
                        if(inside(ny,nx))
                        {
                            a[ny][nx]=!a[ny][nx];
                        }
                    }
                }
            }
        }
        if(check())
        {
            ans=min(ans,cnt);
        }
        return;
    }
    for(int i=index; i<N; i++)
    {
        if(visited[i]==0)
        {
            visited[i]=1;
            v.push_back(i);
            dfs(i,size,depth+1);
            v.pop_back();
            visited[i]=0;
        }
    }
}
bool check(){
    for(int i=0; i<N; i++)
    {
        if(a[N-1][i]==1)
        {
            return false;
        }
    }
    return true;
}
bool inside(int ny,int nx){
    if(0<=ny&&ny<N&&0<=nx&&nx<N)
    {
        return true;
    }
    else
    {
        return false;
    }
}