백준 14939 - 불 끄기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14939

14939번: 불 끄기

비트마스킹을 이용한 문제입니다. 

구현하는 방법을 떠올리는게 어려웠던 문제입니다.

한 곳의 불을 끄면 해당 위치부터 상하좌우의 값이 바뀌게 됩니다.

 

가로, 세로가 모두 10의 크기이기에 모든 경우를 확인하여면 2^100인 경우가 나오게 됩니다. -> 시간 초과가 생깁니다.

이 문제를 풀기 위해선 2가지를 생각해야하는데,

1. 한 번 누르면 다시 누를 필요가 없다. -> 똑같은 칸을 2번 누르면 안누르는 것과 같아진다.

2. 어떤 순서로 누르든 결과는 같다. -> (1, 1) -> (2, 1)과 (2, 1) -> (1, 1)과 같이 같은 곳을 다른 순서로 눌러도 결과는 같다.

 

이제 두방법을 기저에 두고 첫줄만 모든 경우를 확인하는 방법으로 문제를 풀 것입니다.

다음과 같이 첫번째 줄의 검은 색 부분을 눌렀을 때, 밑의 파란색 부분을 당연하게 누를 것입니다.

왜냐하면 다음 줄로 넘어가는 순간 검은 색 칸에 대한 부분을 건들 수 없기 때문입니다.

그렇다면 첫번째 줄을 어떻게 하냐에 따라 불을 어떻게 끌지를 정할 수 있다는 의미가 됩니다.

 

∴ 첫번째 줄에 대해서만 모든 경우를 탐색합니다 -> 2^10

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#define INF 987654321

using namespace std;

char map[11][11], copy_map[11][11];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void turn_on(int x, int y){ //불을 키고끄는 부분입니다.
    if(copy_map[x][y] == 'O') copy_map[x][y] = '#';
    else copy_map[x][y] = 'O';
    for(int i = 0; i < 4; i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10){ // map에 범위에 맞는지 확인
            if(copy_map[xx][yy] == 'O') copy_map[xx][yy] = '#';
            else copy_map[xx][yy] = 'O';
        }
    }
}

void reset_map(){ // map을 복사한다.
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            copy_map[i][j] = map[i][j];
        }
    }
}

bool all_light_on(){ // 불이 전부 꺼져있으면 true 아니면 false를 return한다.
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            if(copy_map[i][j] == 'O') return false;
        }
    }
    return true;
}

void solve(){
    int ans = INF; // 최소 횟수 저장
    for(int step = 0; step < (1 << 10); step++){ // 첫째줄에 나올 수 있는 경우 모두 확인
        int cnt = 0;
        reset_map();
        for(int i = 0; i < 10; i++){ // 첫번째 줄에 불이 켜져있는 부분을 확인
            if(step & (1 << i)){
                cnt++;
                turn_on(0, i);
            }
        }
        for(int i = 1; i < 10; i++){ // 첫줄에 따라 2번째 줄부터 어떤 곳을 꺼야하는지 확인
            for(int j = 0; j < 10; j++){
                if(copy_map[i-1][j] == 'O'){
                    turn_on(i, j);
                    cnt++;
                }
            }
        }
        if(all_light_on()) ans = min(ans, cnt);
    }
    if(ans == INF) cout << "-1";
    else cout << ans;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#define INF 987654321

using namespace std;

char map[11][11], copy_map[11][11];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void turn_on(int x, int y){
    if(copy_map[x][y] == 'O') copy_map[x][y] = '#';
    else copy_map[x][y] = 'O';
    for(int i = 0; i < 4; i++){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10){
            if(copy_map[xx][yy] == 'O') copy_map[xx][yy] = '#';
            else copy_map[xx][yy] = 'O';
        }
    }
}

void reset_map(){
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            copy_map[i][j] = map[i][j];
        }
    }
}

bool all_light_on(){
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            if(copy_map[i][j] == 'O') return false;
        }
    }
    return true;
}

void solve(){
    int ans = INF;
    for(int step = 0; step < (1 << 10); step++){
        int cnt = 0;
        reset_map();
        for(int i = 0; i < 10; i++){ 
            if(step & (1 << i)){
                cnt++;
                turn_on(0, i);
            }
        }
        for(int i = 1; i < 10; i++){
            for(int j = 0; j < 10; j++){
                if(copy_map[i-1][j] == 'O'){
                    turn_on(i, j);
                    cnt++;
                }
            }
        }
        if(all_light_on()) ans = min(ans, cnt);
    }
    if(ans == INF) cout << "-1";
    else cout << ans;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i < 10; i++){
        for(int j = 0; j < 10; j++){
            cin >> map[i][j];
        }
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요