문제
https://www.acmicpc.net/problem/14939
입력
10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다.
출력
모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.
풀이
제한조건
- #과 O외에는 입력으로 주어지지 않는다.
접근방법
'부분집합 + 그리디'
입력의 크기가 크지 않다. (10 x 10)
문제의 접근 방법에 대해서 생각해보자.
우선 누르는 순서는 아무런 상관이 없다.
또한 입력의 크기가 충분히 작기는 하지만, 모든 위치에 대해서 끄거나 켜는
다시말해 완전탐색으로 수행한다면, 2^100으로 너무 커진다.
조금 더 쉽게 생각하기 위해 머리를 굴려보자.
스위치를 하나 누르게 된다면, 십자 모양으로 모두 영향을 끼친다.
어떻게 하면, 최소한의 탐색으로 알 수 있을까..?
아래와 같이 접근해보자.
1. 가장 윗 줄의 전구 스위치 중, 부분집합 생성하기.
2. 두 번째 줄부터 탐색하며 아래로 내려가기.
3. 켜진 불이 있는지 확인하기.1-2 과정을 수행하는 근본적인 이유는 다음과 같다.
아래와 같은 입력을 가정해보자
####O##### ##########
########## ###OOO####
########## ####O#####
########## ##########
########## ##########
########## -> ##########
########## ##########
########## ##########
########## ##########
########## ##########편의를 위해 입력에서 첫 번째 줄과 나머지 줄을 분리하여 생각해보자.
첫 번째 줄의 켜진 전구를 끄기 위해서 2가지 방법이 존재한다.
1. 해당 위치에서 스위치를 누른다.
2. 해당 위치의 아래에서 스위치를 누른다.
여기서 1번 방법을 선택하게 된다면, 탐색과정에서 계속 상하좌우로 영향을 준다.
이는 이중 반복문을 수행하면서 탐색을 할 때, 이미 지나온 자리에 대해서 계속 영향을 미치기 때문에 1번만에 원활하게 결과를 추론하기 어렵다.
하지만 2번 방법을 선택하게 된다면 특정 위치의 바로 위의 전구 상태를 유일하게 마지막으로 변경할 수 있게 된다.
( 이중 반복문의 탐색 순서를 생각해보자.)
이를 떠올리며 아래로 이어서 가보자.
1. 가장 윗 줄의 전구 스위치 중, 부분집합 생성하기.
가장 윗 줄에 해당 하는 전구 스위치 중 부분집합을 생성해보자.
부분집합에서 선택된 자리는 항상 스위치를 누르는 자리이다.
가장 윗 줄에 대해서 선택된 부분집합에 대해서 스위치를 모두 눌러보자.
부분집합을 생성하는 과정은 비트마스크와 재귀를 이용한 방법 어떤것도 상관없다.
(비트마스킹을 통해 모든 경우 (1024가지)를 표현하는 것이 재귀로 depth 10까지 내려가는것 보다 합리적이라 생각하여 비트마스킹을 사용함.)
2. 두 번째 줄부터 탐색하며 아래로 내려가기.
첫 번째가 이제 고정되었으므로, 이제 아랫줄은 항상 윗줄을 켜진 전구를 끄는 방향으로 진행한다.
각 좌표를 탐색하며, 바로 위의 전구가 켜져있다면, 현재 자리에서 스위치를 눌러서 꺼주도록 하자.
이중 반복문의 구조 상, 지금 스위치로 상태를 바꿔주지 않는다면, 다시 탐색하지 않는 한, 영원히 바로 위 전구의 상태를 변경할 수 없다.
3. 켜진 불이 있는지 확인하기.
모든 탐색이 종료되었다면, 전구가 켜진것이 있는지 확인하고 최솟값을 갱신하자.
전체를 탐색하여도 되지만, 우리는 그리디하게 위에서 아래로 내려오며 반드시 필요한 지점에서만 스위치를 눌러왔기에, 가장 마지막 줄만 확인하여도 된다.
( 윗칸의 전구를 아래칸에서 변경했고, 반복문이 가장 아래쪽 줄에서 종료되므로
마지막 줄에서 스위치를 누르는것은 좌우로만 영향을 미친다는 말)
아주 욕심이 가득하게, 그리디하게 접근하면 매우 간단한 문제이다.
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
public class Main {
static int SIZE = 10;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static Map<Character, Character> map;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// init
char[][] arr = new char[SIZE][SIZE];
char[][] simulationArr = new char[SIZE][SIZE];
for (int i = 0; i < SIZE; ++i)
arr[i] = in.readLine().toCharArray();
map = new HashMap<>();
map.put('#', 'O');
map.put('O', '#');
int result = Integer.MAX_VALUE;
// 모든 경우의 수
for (int state = 0; state < (1 << SIZE); ++state) {
int count = 0;
deepCopy(arr, simulationArr); // arr의 값을 simulationArr로 복사.
// 첫 줄은 경우의 수를 따져서 처리한다.
for (int j = 0; j < SIZE; ++j) {
// 특정 위치를 누르는 선택
int bitNum = 1 << j;
if ((state & bitNum) == bitNum) {
count++;
pressButton(0, j, simulationArr);
}
}
// 나머지 줄은 윗 줄의 결과에 종속된다.
for (int i = 1; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
// 불이 켜져있다면, 지금 꺼야한다.
if (simulationArr[i - 1][j] == 'O') {
count++;
pressButton(i, j, simulationArr);
}
}
}
if (isValidate(simulationArr[SIZE-1]))
result = Math.min(result, count);
}
if (result == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(result);
}
private static boolean isValidate(char[] chars) {
for (char c : chars)
if (c == 'O')
return false;
return true;
}
private static void deepCopy(char[][] arr, char[][] simulationArr) {
for (int i = 0; i < SIZE; ++i)
for (int j = 0; j < SIZE; ++j)
simulationArr[i][j] = arr[i][j];
}
private static void pressButton(int x, int y, char[][] simulationArr) {
// 현재 위치 변경
simulationArr[x][y] = map.get(simulationArr[x][y]);
// 인접 4방향 변경
for (int d = 0; d < 4; ++d) {
int nextX = x + dx[d];
int nextY = y + dy[d];
if (isInRange(nextX, nextY))
simulationArr[nextX][nextY] = map.get(simulationArr[nextX][nextY]);
}
}
public static boolean isInRange(int x, int y) {
if (0 <= x && x < SIZE && 0 <= y && y < SIZE)
return true;
return false;
}
public static int stoi(String s) {
return Integer.parseInt(s);
}
}
}