[백준 14939] 불 끄기 C++

14939번: 불 끄기

그리디 알고리즘

---

1. 문제해결 아이디어

전구의 가장 윗 라인에서 스위치를 누르는 모든 경우(2^10=1024)를 시도해 본다.

그리고 두 번째 라인을 부터는 현재 열의 바로 윗 행의 전구가 켜져있는지 꺼져있는지에 따라서 스위치를 누를지 말지가 결정된다. 만약 바로 윗 행의 전구가 켜져있는데 현재 열의 스위치를 누르지 않는다면 앞으로 윗 행의 전구를 끌 방법은 없기 때문이다.(방향 : 왼쪽 상단부터 오른쪽 하단)

이렇게 하면 1~9 행은 모든 전구가 꺼질 수 밖에 없고,

이때 10 행의 전구를 모두 끌 수 있는지에 따라서 답이 나뉘게 된다.

 

처음에 dfs를 사용해서 1행의 스위치를 누르는 모든 경우를 시도해 보려고 했다.

그런데 눌렀던 스위치를 다시 눌러서 기존의 상태로 돌리는 백트래킹 과정에서 오류가 계속 생겨서 

1024번의 반복문을 그냥 돌렸다.

---

2. 코드 설명

<+9> ~ <+18> : r, c 에있는 전구의 스위치를 눌러주는 함수

<+20> ~ <+37> : 1행의 전구를 누르는 모든 경우에 대해서 답을 구할 수 있는지 알아내는 함수

<+50> : i 번째 행의 전구를 눌러야 하는지 비트마스킹을 통해 빠르게 알 수 있다.

           나는 여기서 k & (1 << i) 를 k && (1 << i)로 처음에 잘못 써줘서 계속 틀렸다.

           너무 기본적인 코드를 한 글자 실수하니까 디버깅할때 뭐가 틀렸는지 찾는데 너무 오래걸렸다. 

 

#include <iostream>
 
#define INF 1e9+7
using namespace std;
 
int Map[11][11], TMap[11][11], result = INF, cnt = 0;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
void turn(int r, int c){
    TMap[r][c] = !TMap[r][c];
    
    for(int i = 0; i < 4; i++){
        int nr = r + dr[i];
        int nc = c + dc[i];
        if(nr < 0 || nc < 0 || nr >= 10 || nc >= 10) continue;
        TMap[nr][nc] = !TMap[nr][nc];
    }
}
 
bool is_solved(){
    // 현재 열의 바로 위 전구가 1이면 꺼야하므로 현재 전구스위치를 누른다
    for(int r = 1; r < 10; r++){
        for(int c = 0; c < 10; c++){
            if(TMap[r-1][c]){
                turn(r, c);
                cnt++;
            }
        }
    }
    
    // 마지막 행에 전구가 켜져있으면 끌 수 없으므로 false
    for(int c = 0; c < 10; c++){
        if(TMap[9][c]) return false;
    }
    
    return true;
}
 
void solve(){
    for(int k = 0; k < 1024; k++){
        // Map 복사
        for(int r = 0 ; r < 10 ; r++){
            for(int c = 0 ; c < 10 ; c++){
                TMap[r][c] = Map[r][c];
            }
        }   
        
        cnt = 0;
        for(int i = 0; i < 10; i++){
            if(k & (1 << i)){
                cnt++;
                turn(0, i);
            }
        }
        
        if(is_solved()) result = min(result, cnt);
    }
    
    if(result == INF) cout << -1;
    else cout << result;
}
 
// dfs를 사용하면 이 문제에서 전구의 상태를 백트래킹하기 힘들어 보인다....
 
//void dfs(int r, int c){
//    if(c == 10){
//        if(is_solved()) result = min(result, cnt);
//        return;
//    }
//    dfs(r, c+1);
//    
//    turn(r, c, 0);
//    dfs(r, c+1);
//    turn(r, c, 0);
//    
//}
 
void input(){
    string str;
    for(int i = 0; i < 10; i++){
        cin >> str;
        for(int j = 0; j < 10; j++){
            if(str[j] == 'O') Map[i][j] = 1;
            else Map[i][j] = 0;
        }
    }
}
 
int main(){
    input();
    solve();
    
    return 0;
}