BOJ 14939

25 Apr 2020 • ProblemSolving

불 끄기

문제출처

문제 해석

  • 전구 100개의 스위칭 상태가 10x10모양으로 주어질 때, 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 구하는 문제입니다.
  • 스위치를 누르면 그 전구와 위,아래,왼쪽,오른쪽에 있는 전구의 상태가 바뀝니다.

설계(20)

  • 모든 좌표를 전부 껐다가 켜는 완전탐색 방식으로는 시간복잡도가 너무나 커서 해결하기 어렵습니다.
  • 그런데, 이런류의 문제는 그리디하게 첫번째 행의 상태를 정해주면 나머지는 자동으로 채워지는 방식으로 되어있습니다.
  • 약간 오셀로 문제와 비슷한게, 먼저 첫 행에서 스위치를 누를 위치를 정해줍니다.
  • 나올 수 있는 상태의 경우의 수는 2^10입니다.
  • 첫행을 전부 스위칭한 후, 다음행부터 각 좌표의 바로 위의 전구가 켜져있으면 스위칭을 하는 방식으로 진행합니다.
  • 위를 제외한 나머지 전구들은 아래의 행에서 모두 지워질 것이기 때문에 고려하지 않습니다.
  • 주의할 점은, 전구를 끌 수 없는 경우가 있습니다.
  • 예를들어, 위의 방식으로 모두 전구를 껐는데 마지막 행의 경우에는 못 끄는 전구가 나올 수 있습니다.
  • 모든 전구를 못끄는 경우가 이에 해당하므로, 마지막 행을 조사하여 전구가 전부 꺼졌는지 확인할 필요가 있습니다.
  • 종합적으로 시간복잡도를 계산해보면, 첫행의 스위칭 경우의 수O(2^10)x나머지 좌표 스위칭O(9x10)로 완전탐색으로 문제를 해결할 수 있습니다.

구현(40)

코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXN 10
#define INF 987654321

int map[MAXN][MAXN];
int copy_map[MAXN][MAXN];
int ans = INF;
int dx[] = {0,0,0,1,-1};
int dy[] = {0,1,-1,0,0};
bool is_range(int x, int y ){
    return (x>=0 && y>=0 && x <MAXN && y<MAXN);
}
void go(int x , int y){
    for (int i = 0 ;i< 5; i++){
        int nx= x +dx[i];
        int ny= y + dy[i];
        if (!is_range(nx,ny)) continue;
        copy_map[nx][ny] = (copy_map[nx][ny]+1)%2;

    }
}


int main(){

    for (int i = 0 ; i <MAXN; i++){
        for (int j =0 ;j<MAXN; j++){
            char tmp;
            scanf(" %1c",&tmp);
            if (tmp == 'O') map[i][j] = 1;
        }
    }
    for (int i = 0; i < (1<< MAXN); i++){
        int cnt = 0;
        memcpy(copy_map,map,sizeof(map));
        for (int j = 0; j< MAXN; j++){
            if (i & (1<<j)){
                go(0,j);
                cnt++;
            }
        }
        for (int j = 1; j<MAXN; j++){
            for (int k = 0; k< MAXN; k++){
                // 위쪽이 켜져있으면 스위치 누름
                if (copy_map[j-1][k]){
                    go(j,k);
                    cnt++;
                }
            }
        }
        bool flag = false;
        for (int j = 0; j< MAXN; j++){
            if (copy_map[MAXN-1][j]) {
                flag=  true;
                break;
            }
        }
        if (!flag) ans = min(ans,cnt);
    }
    if (ans == INF) cout <<-1;
    else cout << ans <<"\n";
    return 0;
}
디버깅
  • 깜빡하고 마지막 행으로 불가능 여부를 탐색하지 않았습니다.
제출결과
  • 0 ms

마무리

  • 그리디 + 완전탐색 문제였습니다.
  • 그리디문제 자체가 정형화되어있지 않고 약간의 아이디어가 필요한 문제로, 이를 생각하지 못하면 문제해결이 어렵습니다.
 BOJ

Related Posts