문제
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
접근
이 문제는 몇 년전 소마 코테에 나온 제일 어려운 문제랑 비슷하다고 해서 언젠가 풀어보려고 즐찾을 해뒀었다.
예전에 이 문제를 처음 봤을 때는 사실 아무 생각도 안 들었었는데, BOJ 1285 동전 뒤집기 문제를 푼 후에 다시 보니 두 문제가 꽤나 유사하다는 생각이 들었다.
실제로 두 문제 모두 불을 껐다 켜거나 동전을 뒤집거나 하는 토글 퍼즐 계열이라 풀이 패턴이 비슷했고, 그래서 문제 이해가 좀 수월했던 것 같다.
두 문제 모두 모든 경우의 수에 대해 완전 탐색을 수행하면 시간 초과가 발생한다.
하지만, 일부 요소를 켜거나 뒤집는 것만으로 다른 요소들의 최적 상태가 그리디하게 강제적으로 정해지기에 그 일부 요소에 대해서만 완전 탐색을 수행하면 탐색 가짓수를 크게 줄일 수 있다.
동전 뒤집기 문제에서는 뒤집을 행을 일단 먼저 선택하면 열을 선택할 때는 앞면이 더 많은 열을 선택하는 것이 반드시 최적이 되기 때문에 뒤집을 행을 선택하는 모든 경우의 수에 대해서만 탐색하면 됐던 거다.
그렇다면 이 문제에서는 전체 상태를 강제하게 하기 위해 결정되어야 할 일부 요소가 무엇인지를 생각해야 했다.
이 문제의 목표는 모든 전구를 다 끄는 것이기 때문에, 윗행에 켜져 있는 전구가 있다면 바로 아래 행에서라도 반드시 꺼야 한다. 그래서 반드시 다음이 성립한다.
- 현재 위치에서 바로 윗행의 전구가 켜져 있다면,
바로 윗행의 전구를 끄기 위해 현재 위치의 스위치를 눌러야만 한다. - 현재 위치의 바로 윗행의 전구가 꺼져 있다면,
현재 위치의 전구를 켜 버리면 바로 윗행이 켜져 버리기 때문에 모든 전구를 꺼야 하는 문제의 조건에 위배된다. 따라서 현재 위치의 스위치를 누르지 않아야만 한다.
정리하면, 바로 윗행의 전구가 켜져 있는지 꺼져 있는지에 따라 현재 위치에서 취해야 할 행동은 하나로 정해질 수밖에 없다는 거다.
그러니까 복잡해 보이지만 사실 맨 윗줄, 그러니까 첫 행의 전구 상태만 결정해 주면 그 아래 행들은 연쇄적으로 자동 결정될 수밖에 없게 된다.
전구의 수가 총 100개이기 때문에 완전 탐색을 하면 회의 연산이 필요하다. 반면, 첫 행에 대해서만 브루트포스로 탐색을 수행하고 나머지는 자동 결정하면 연산 횟수가 회로 크게 줄어든다.
약간 여담인데, 만약 이 문제의 목표가 모든 전구를 끄는 게 아니라면 바로 위가 켜져 있으면 무조건 끈다는 이 논리가 성립하지 않을 것이다. 동전 뒤집기 문제는 행 단위로 뒤집기 때문에 모든 동전을 앞면으로 만들지 못하더라도 뒷면의 개수를 최소화하는 게 무조건 가능했다. 하지만 이 문제에 '전구를 다 끄지 못하더라도 최대한 많이 끄자!'라는 동일한 목표를 부여해버리면 구조상 문제를 절대 풀 수 없는 케이스가 존재하게 된다. 그래서 무조건 다 꺼 버리고, 다 끌 수 없으면 그냥 -1을 출력하도록 상황을 단순화했다고 볼 수 있다.
구현
import java.io.*;
import java.util.*;
class Main {
static char[][] bulb = new char[10][10];
static int answer = 101;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < 10; i++) {
String input = br.readLine();
for (int j = 0; j < 10; j++) {
bulb[i][j] = input.charAt(j);
}
}
backtracking(0, 0);
if (answer == 101) {
System.out.println(-1);
return;
}
System.out.println(answer);
}
private static void backtracking(int depth, int firstRowPressCnt) {
if (depth == 10) {
int count = calculatePressCount();
if (count > -1) {
answer = Math.min(answer, count + firstRowPressCnt);
}
return;
}
pressSwitch(0, depth);
backtracking(depth + 1, firstRowPressCnt + 1);
pressSwitch(0, depth);
backtracking(depth + 1, firstRowPressCnt);
}
private static void pressSwitch(List<int[]> pressedList) {
int[] dx = {0, -1, 0, 1, 0};
int[] dy = {0, 0, 1, 0, -1};
for (int[] pressed : pressedList) {
for (int i = 0; i < 5; i++) {
int targetRow = dx[i] + pressed[0];
int targetCol = dy[i] + pressed[1];
if (targetRow >= 0 && targetRow < 10 && targetCol >= 0 && targetCol < 10) {
bulb[targetRow][targetCol] = (bulb[targetRow][targetCol] == '#')? 'O' : '#';
}
}
}
}
private static void pressSwitch(int row, int col) {
int[] dx = {0, -1, 0, 1, 0};
int[] dy = {0, 0, 1, 0, -1};
for (int i = 0; i < 5; i++) {
int targetRow = dx[i] + row;
int targetCol = dy[i] + col;
if (targetRow >= 0 && targetRow < 10 && targetCol >= 0 && targetCol < 10) {
bulb[targetRow][targetCol] = (bulb[targetRow][targetCol] == '#')? 'O' : '#';
}
}
}
private static int calculatePressCount() {
List<int[]> pressedList = new ArrayList<>();
for (int i = 1; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (bulb[i - 1][j] == 'O') {
pressSwitch(i, j);
pressedList.add(new int[] {i, j});
}
}
}
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (bulb[i][j] == 'O') {
pressSwitch(pressedList);
return -1;
}
}
}
pressSwitch(pressedList);
return pressedList.size();
}
}
