[백준/JAVA] 14939번 불 끄기

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

14939번: 불 끄기

문제분석

10X10 크기의 방에 불이 켜진곳과 안 켜진곳이 있다

불이 켜진곳은 O 불이 켜지지 않은 곳은 #로 입력이 들어온다.

각 방의 스위치를 누르면 그 방과 상하좌우 방의 불의 상태가 바뀐다. ( 켜져있으면 꺼지고, 꺼져있으면 켜진다.)

모든 방의 불을 끄도록 하고싶을 때 스위치 조작의 최소 횟수를 구하는 문제이다. 

 

코드

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

/**
 * 백준 14939 불 끄기. 완전탐색 사용
 *
 * @author 2sssg
 */
public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	// 기본 입력 배열
	static int[][] arr = new int[10][10];
	// 임시 배열
	static int[][] temparr = new int[10][10];
	static int tempanswer, answer = Integer.MAX_VALUE;
	static int[] dx = {0, 0, 1, 0, -1};
	static int[] dy = {0, 1, 0, -1, 0};


	/**
	 * origin 배열을 풀이에 사용할 배열로 복사해주는 함수
	 */
	static void init() {
		tempanswer = 0;
		for (int i = 0; i < 10; ++i) {
			temparr[i] = arr[i].clone();
		}
	}

	/**
	 * 눌러지는 방의 좌표를 받고 상하좌우방의 상태값을 변경하는 함수입니다.
	 *
	 * @param x 클릭할 x좌표
	 * @param y 클릭할 y좌표
	 */
	static void click(int x, int y) {
		for (int i = 0; i < 5; ++i) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= 10 || ny >= 10) {
				continue;
			}
			temparr[nx][ny] ^= 1;
		}
	}

	public static void main(String[] args) throws IOException {

		// 각 줄을 입력받고 불이 켜져있으면 1 꺼져있으면 0
		for (int i = 0; i < 10; ++i) {
			arr[i] = Arrays.stream(br.readLine().split("")).mapToInt(p -> p.equals("#") ? 0 : 1)
				.toArray();
		}

		// 0000000000 ~ 1111111111 비트 순회 (1024가지)
		for (int i = 0; i < 1024; ++i) {
			//초기화
			init();

			// 첫 번째 줄 불 켜기
			for (int j = 1; j <= 10; ++j) {
				int num = 1024;
				num = num >> j;
				if ((i & num) > 0) {
					tempanswer++;
					click(0, j - 1);
				}
			}

			// 윗줄의 자신의 열이 불이 켜져있으면 불을 꺼주기
			for (int j = 1; j < 10; ++j) {
				for (int k = 0; k < 10; ++k) {
					if (temparr[j - 1][k] == 1) {
						tempanswer++;
						click(j, k);
					}
				}
			}

			// 0~9행은 모두 불이 꺼져있음
			// 마지막줄에 불이켜진 방이있는지만 확인해보면 됨
			if (Arrays.stream(temparr[9]).sum() == 0) {
				answer = Math.min(answer, tempanswer);
			}
		}

		// 초기값(0xffffffff)이면 불을 다 끌수있는 방법이 없음
		System.out.println(answer == Integer.MAX_VALUE ? "-1" : answer);
	}
}

 

문제풀이

모든 방의 개수는 10*10 즉 100개이다. 

잘못된 방법1. 100개를 전부 끄거나 켜보는 방법 => 2^100회로 시간 초과

잘못된 방법2. 하나의 방을 기준으로 가장많은 불이 켜져있는 방의 스위치를 누르는 방법 => 무한루프 가능성o 

단서1. 하나의 열은 내가 원하는 대로 변경이 가능함 

단서2. 하나의 블럭 선택기준, 거리가 2이상인 블럭에 대해서는 영향을 미치지 않음.

풀이 =>

1. 1행의 불이 켜진 열에 대해 2행의 해당열의 스위치를 작동시킨다.

2. 2행의 작업이 끝났을 시기에는 1행은 모두 불이 꺼져있을 것이다.

3. 2~k행을 작업한다면 1~k-1행의 모든 방은 불이 꺼져있을 것이다.

4. k행에도 불이 다 꺼져있다면 모든 방의 불은 꺼져있는 것이다.

따라서 첫 번째 행에대한 불을 켜고 끌 수 있는 모든 경우에수에 대해 위의 작업을 하고

각 경우의수의 최소값이 모든 방의 불을 끌 수 있는 최소값이 된다.

O(2^m*N*M) (n=10, m=10) 으로 시간초과가 되지않고 통과할 수 있다.