백준 14939 [불 끄기]

문제

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라

입력

10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.

출력

모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.

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

14939번: 불 끄기

 

---

 

 이 문제를 보자마자 '비트마스킹을 이용하겠구나!'라는 생각은 했지만 그 이상의 생각을 해내지 못했다. 완전탐색은 2^100이므로 당연히 아니고 비트마스킹을 이용한 dp를 하려해도 비트가 너무 커져서 할 수 없었다. 이렇게 이 문제를 본 첫째 날은 고민만 하다 문제를 넘기게 되었다.

 

 

 다음날 문제의 알고리즘 분류를 보게 되었고 거기에 적혀있는 건 다음 3가지였다. 

 

    1. 그리디 알고리즘

    2. 브루트포스 알고리즘

    3. 비트마스킹

 

3번은 알고있었고 1과 2를 합쳐 생각해보니 그리디 알고리즘을 통한 완전탐색으로 풀어야한다는 결론이 나왔다. 그래서 둘째 날은 그리디 방법에 대해 고민을 했다. 고민 끝에 생각한 방법은 전체 전구 중 본인 포함 상하좌우에 불이 가장 많이 켜진 전구부터 누르는 방법이다. 실제로 이를 코드로 구현하니 문제에서 주어진 기본 예제는 통과할 수 있었다. 하지만 실제 채점을 받아보니 '틀렸습니다'가 떴고 반례에 대해 생각해보니 다음과 같은 경우에서 정답을 맞추지 못한다는 것을 알아냈다.

 

예제)

1이 불이 켜진경우이고 0이 불이 꺼진 경우이다.

0	0	0	0	0	0	0
0	0	0	1	0	0	0
0	0	0	1	0	0	0
0	1	1	0	1	1	0
0	0	0	1	0	0	0
0	0	0	1	0	0	0
0	0	0	0	0	0	0

 실제로는 빨간색 1을 4개 누르면 불이 다 꺼지므로 답은 4가 된다. 하지만 내가 생각한 방법으로 풀면 처음부터 주변에 불이 가장 많이 들어와있는 보라색 0을 누르게 되고 그러면 이제 불을 전부 끄는 방법을 찾을 수 없어 -1이 출력된다. 결국 둘째 날도 답을 찾지 못하고 넘어가버렸다.

 

 셋째 날은 이 문제에 대한 풀이를 찾아봤다. 찾아보니 그리디 방법이 나와 달랐고 그 규칙은 다음과 같다.

 

    1. 전구의 첫번째 줄부터 마지막 줄까지 순서대로 버튼을 누른다.

    2. 우선 첫번째 줄은 완전탐색으로 1024개의 경우의 수를 전부 탐색한다.

    3. 둘째 줄부터는 이전 줄에 불이 켜져있으면 현재 줄의 버튼을 누르는 식으로 이전 줄의 불을 전부 끈다.

    4. 이 방법으로 마지막 줄의 버튼까지 다 눌렀을 때 불이 전부 꺼지면 누른 버튼의 개수를, 그게 아니면 -1을 기록한다.

    5. 첫째줄의 1024개의 경우의 수로부터 마지막 줄 탐색까지 모든 경우의 최댓값을 출력한다.

 

이 방법으로 풀면 (첫째줄의 경우의수 1024) * (줄마다 불이 켜졌는지 10번 탐색) * (9개의 줄을 탐색) = O(1024 * 9 * 10)의 시간복잡도로 시간안에 문제를 풀 수 있다. 코드는 다음과 같다.

 

 

import java.io.*;
import java.util.*;
class Main {
    static int num = -1;
    static boolean[][] check = new boolean[10][10];
    static int[] di = {0, -1, 0, 1, 0};
    static int[] dj = {-1, 0, 1, 0, 0};
    static boolean check(int[] bulb){
        boolean check = true;
        for (int i = 0; i < 10; i++)
            if (bulb[i] != 0) check = false;
        return check;
    }
    static void dfs(int[] bulb, int row, int cnt) {
        if (row == 10){
            if (check(bulb))
                num = Math.max(num, cnt);
        }else {
            for (int i = 0; i < 10; i++){
                if ((bulb[row - 1] & (1 << i)) > 0) {
                    change(bulb, row, i);
                    cnt++;
                }
            }
            dfs(bulb, row + 1, cnt);
        }
    }
    static void change(int[] bulb, int x, int y){
        for (int k = 0; k < 5; k++){
            int i = x + di[k];
            int j = y + dj[k];
            if (i >= 0 && i < 10 && j >= 0 && j < 10) {
                if ((bulb[i] & (1 << j)) > 0)
                    bulb[i] = bulb[i] & ~(1 << j);
                else
                    bulb[i] = bulb[i] | (1 << j);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] bulb = new int[10];
        for (int i = 0; i < 10; i++){
            String s = br.readLine();
            for (int j = 0; j < 10; j++)
                if (s.charAt(j) == 'O') bulb[i] = bulb[i] | (1 << j);
        }
        for (int i = 0; i <= 1024; i++){
            int[] new_bulb = bulb.clone();
            int cnt = 0;
            for (int j = 0; j < 10; j++)
                if ((i & (1 << j)) > 0) {
                    change(new_bulb, 0, j);
                    cnt++;
                }
            dfs(new_bulb, 1, cnt);
        }
        System.out.println(num);
    }
}

 

푸는 방법을 알고 코드를 짜서 문제를 풀 수 있었지만 아직 다른 문제가 나왔을 때 내가 이런 방법을 생각할 수 있을까라는 의문이 든다. 좀 더 여러 방법을 생각해 볼 수 있게 다양한 문제를 풀어야겠다.