[Java | 시뮬레이션 | 14939번 | 플4] 불 끄기

☑️ 문제

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

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

 

입력

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

 

출력

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

 

예제 입력1

#O########
OOO#######
#O########
####OO####
###O##O###
####OO####
##########
########O#
#######OOO
########O#

 

예제 출력1

4

 

☄️ 정답코드

import java.io.*;

public class Main {
    static final int SIZE = 10;
    static final int INF = Integer.MAX_VALUE;
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        char[][] map = new char[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            map[i] = br.readLine().toCharArray();

        }

        int answer = INF;
        char[][] tmp = new char[SIZE][SIZE];
        for (int i = 0; i < (1<<SIZE); i++) {
            deepCopy(map, tmp);

            int cnt = simulation(tmp, i, 0);

            if(isAllOff(tmp)) {
                answer = Math.min(answer, cnt);
            }
        }

        System.out.println(answer == INF ? -1 : answer);
    }

    static boolean isAllOff(char[][] tmp) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if(tmp[i][j] == 'O') return false;
            }
        }

        return true;
    }

    static int simulation(char[][] tmp, int c, int cnt) {
        for (int i = 0; i < SIZE; i++) {
            if((c & (1<<i)) != 0) {
                lightSwitch(tmp, 0, i);
                cnt++;
            }
        }

        for (int i = 1; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if(tmp[i-1][j] == 'O') {
                    lightSwitch(tmp, i, j);
                    cnt++;
                }
            }
        }

        return cnt;
    }

    static void lightSwitch(char[][] tmp, int i, int j) {
        tmp[i][j] = switchOnOff(tmp[i][j]);

        for (int[] dir : dirs) {
            int ni = i + dir[0];
            int nj = j + dir[1];

            if (ni < 0 || ni >= SIZE || nj < 0 || nj >= SIZE) continue;

            tmp[ni][nj] = switchOnOff(tmp[ni][nj]);
        }
    }

    static char switchOnOff(char c) {
        return c == '#' ? 'O' : '#';
    }

    static void deepCopy(char[][] map, char[][] tmp) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                tmp[i][j] = map[i][j];
            }
        }
    }
}

🪐 풀이

시뮬레이션 + 그리디 + 비트

시뮬레이션 문제이지만, 살짝의 그리디적인 부분이 있는 문제였다.

비트를 연습하기 위해 이번에는 비트를 이용해 풀었다!!

 

✅ 그리디적으로 생각해야 할 부분

전구의 개수가 100개로 고정되어있다.

생각보다 적네? 라고 할 수도 있지만

모든 경우를 생각해보면 한 칸에 켜진 경우, 꺼진 경우가 있기 때문에

무려 2^100이다.

 

위에서 아래로, 왼쪽에서 오른쪽으로 천천히 탐색한다면 위, 왼으로 다시 돌아갈 수 없다.

 

이 점을 생각해보면 첫번째 줄이 확정되면 그 외 줄은 줄줄이 소시지로 바뀐다.

 

첫번째 줄의 경우의 수는 2^10이고, 그 외의 줄은 대략적으로 100이라고 치면,

102,400 대략 10만이라 하면 충분히 괜찮은 수이다!

 

✅ 첫 번째 줄의 모든 경우의 수를 탐색

i는 0000000000(2) ~ 1111111111(2)이 될 것이고, 1인 위치의 전구를 눌러야 한다는 의미이다.

static final int SIZE = 10;

for (int i = 0; i < (1<<SIZE); i++) {
    deepCopy(map, tmp);
  
    int cnt = simulation(tmp, i, 0);
  
    // 다 꺼지면 answer 확인해서 갱신
    if(isAllOff(tmp)) {
        answer = Math.min(answer, cnt);
    }
}

 

✅ simulation(char[][] tmp, int c, int cnt)

static int simulation(char[][] tmp, int c, int cnt) {
    // i번째 비트가 1이면 해당 전구 누름
    for (int i = 0; i < SIZE; i++) {
        if((c & (1<<i)) != 0) {
            lightSwitch(tmp, 0, i);
            cnt++;
        }
    }

    for (int i = 1; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            if(tmp[i-1][j] == 'O') {	// 위쪽 전구가 켜져있으면 눌러야 함!
                lightSwitch(tmp, i, j);
                cnt++;
            }
        }
    }

    return cnt;
}