[백준/BOJ] 14939 불 끄기 - JAVA

백준 BOJ 14939 불 끄기 - JAVA

문제

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

문제 분석

조건

• 방의 크기는 10X10으로 일정하다.
• 불이 켜진 곳은 'O', 꺼진 곳은 '#'으로 표현된다.
• 스위치를 누른 곳과 상하좌우의 상태가 반전된다.
• 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수 출력
• 모두 끌 수 없을 경우 -1 출력

풀이방법

• 하나의 스위치 상태를 바꾸면 상하좌우가 전부 반전되므로 1행의 상태가 결정이 된다면 그 아래는 자동으로 결정됨
• 한 행의 스위치가 10개이므로 총경우의 수는 2^10개로 많지 않음
• 위 행을 기준으로 켜진 스위치를 끈다면 해당 행의 윗 행은 전부 스위치가 꺼지게 됨
• 마지막 행에서 위 행을 기준으로 스위치를 껐을 때 켜져 있는 스위치가 남아있을 경우 불가능함

+

• 비트마스킹을 사용하여 문제를 풀고 싶었음.
  왜냐하면 1. 방의 불 상태가 켜짐/꺼짐의 상태로 0과 1로 표현하기에 너무 좋아 보임.
  2. 마지막 행에 켜져 있는 스위치가 있는지 판단할 때 `if(위치=='O')`로 비교하기보단 모든 스위치가 꺼져 0인 상태이므로 0인지 비교하는 게 좋아 보였음
  3. 스위치 켜고 끌 때 상하좌우/해당칸을 켜져 있나 `if-else`를 사용하여 판단하기보다는 그냥 XOR연산을 하면 되기 때문
  4. 왠지 알고리즘 고수들이 비트를 잘 사용하는 거 같아서..
  • 하지만 괜히 복잡하게 푼 거 같기도!
• 처음엔 `char [][]` 형태로 초기 상태를 입력받고 복사하면서 `int []` 형태로 바꾸게 구현했다가 처음 입력받으면서 바로 int[] 형태로 받도록 수정했는데 속도차이가 크진 않다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int[] originMap = new int[10];
        //0일 경우 << 해도 0이기 때문에 처음 1로 초기화 해줘야함
        Arrays.fill(originMap, 1);
        for (int r = 0; r < 10; r++) {
            String line = br.readLine();
            for (int c = 0; c < 10; c++) {
                originMap[r] = originMap[r] << 1;
                if (line.charAt(c) == 'O') {
                    originMap[r] |= 1;
                }
            }
        }

        // 1줄 2^10
        int T = 1 << 10;
        int answer = Integer.MAX_VALUE;
        for (int tc = 0; tc < T; tc++) {
            int[] copyMap = Arrays.copyOf(originMap, 10);
            int count = 0;
            for (int c = 0; c < 10; c++) {
                if (((1 << c) & tc) != 0) {
                    turn(copyMap, 0, c);
                    count++;
                }
            }
            //2번째줄부터
            for (int r = 1; r < 10; r++) {
                for (int c = 0; c < 10; c++) {
                    if (copyMap[r - 1] == T) {
                        //윗줄이 전부 스위치가 꺼진 상태
                        break;
                    }
                    if ((copyMap[r - 1] & (1 << c)) > 0) {
                        turn(copyMap, r, c);
                        count++;
                    }
                }
            }
            if (copyMap[9] == T) {
                answer = Math.min(answer, count);
            }
        }
        if (answer == Integer.MAX_VALUE) {
            answer = -1;
        }
        System.out.println(answer);
    }

    private static void turn(int[] map, int r, int c) {
        int[][] dr = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] d : dr) {
            int nextR = r + d[0];
            int nextC = c + d[1];
            if (nextR < 0 || nextR >= 10 || nextC < 0 || nextC >= 10) {
                continue;
            }
            //XOR연산
            map[nextR] = map[nextR] ^ (1 << nextC);
        }
    }
}

결과