BOJ 14927

22 Feb 2020 • ProblemSolving

전구끄기

문제출처

문제 해석

  • 주어진 NxN전구판의 초기상태에서 모든 전구를 끌 수 있는 최소 횟수를 구하는 문제입니다.
  • 만약 전구를 끄고자 하는 좌표를 선택하면, 해당 좌표와 상하좌우로 인접하는 좌표들에 있는 전구들의 상태를 반대로 전환 시킵니다.(0->1 , 1->0)

설계(X)

  • N<=18이므로 백트래킹을 이용하면 누가봐도 시간초과일게 뻔했습니다.O(2N2)
  • 최적화할 만한 아이디어를 얻지 못해 질문검색에 있는 3587jjh님의 아이디어를 참조하였습니다.
  • 여기서 키포인트는 다음과 같습니다.
    1. 퍼즐을 푸는데 각각의 버튼들은 최대 한번만 눌러봐도 됩니다.
    2. 버튼들을 누르는 순서는 상관없습니다.
  • 키포인트를 참조하여 전구판의 첫 행을 누르는 경우를 구합니다.(O(2N)).
  • 두번째 행부터는 좌표를 탐색하면서 이전 행의 좌표의 정보가 1인 열을 찾아서 버튼을 눌러줍니다. O(N2)
  • 만약 마지막 행까지 위와 같이 수행했을 때 모든 전구가 꺼져있으면 최소값을 갱신합니다.
  • 총 시간복잡도는 O(N2*2N)이므로 시간안에 구현이 가능합니다.

구현(30)

코드
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 18
#define INF 987654321

int map[MAXN][MAXN];
int copy_map[MAXN][MAXN];
bool used[MAXN];
int N;
int ans = INF;
void check_map(int x, int y, int arr[][MAXN]){
    if (y>0) arr[x][y-1] = (arr[x][y-1]+1) %2;
    if (x < N-1){
        arr[x+1][y] = (arr[x+1][y]+1)%2;
    }
    if (x > 0){
        arr[x-1][y] = (arr[x-1][y]+1)%2;
    }
    if (y < N-1) arr[x][y+1] = (arr[x][y+1]+1)%2;
    arr[x][y] = (arr[x][y]+1)%2;
}
void dfs(int idx, int cnt){
    memcpy(copy_map,map,sizeof(map));
    int sum = 0;
    for (int i =0; i < N; i++){
        if (used[i]){
            sum++;
            check_map(0,i,copy_map);
        }
    }
    for (int i = 1; i <N; i++){
        for (int j =0 ;j<N;j ++){
            if (copy_map[i-1][j]){
                sum++;
                check_map(i,j,copy_map);
            }
        }
    }
    bool flag = false;
    for (int i = 0; i <N&&!flag; i++){
        if (copy_map[N-1][i]) flag = true;
    }
    if (!flag){
        if (ans > sum) ans = sum;
    }
    if (cnt == N) return;
    for (int i = idx; i < N; i++){
        if (!used[i]){
            used[i] = true;
            dfs(i,cnt+1);
            used[i] =  false;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i =0 ;i < N; i++){
        for (int j =0;j<N;j++){
            cin >> map[i][j];
        }
    }
    dfs(0,0);
    if (ans == INF) cout <<"-1\n";
    else cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 584ms

마무리

  • 백트래킹을 이용하는 문제였습니다. 아이디어를 얻기 어려운 문제이기 때문에 난이도가 높게 책정된 것 같습니다.
  • 비트마스킹으로 더욱 최적화된 구현이 가능하다고 합니다.
 BOJ

Related Posts