내일은 알고리즘

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

처음 문제를 보고, 뭐지 하는 생각이 들었습니다.

문제의 지문 자체는 간결하고 이해도 되는데 이 문제를 어떻게 구현할지 엄두가 안 나더라고요.

그나마 추측할 수 있는 부분은 입력의 크기가 고정되어있고 10x10 사이즈로 작다 보니 완전탐색으로 될 것 같다 정도였습니다. 고민을 좀 해봤지만 명쾌한 아이디어가 안 떠올라, 검색을 통해 접근 법을 찾았고 구현 자체는 어렵지 않았습니다.

핵심아이디어는 이것입니다.

한 줄씩 불꺼진 상태를 고정시키자.

불 켜진 줄을 누르게 되면, 좌 우의 전구가 동시에 on off되기 때문에 확실하게 불이 꺼진 줄을 만드는 방법은 해당 줄의 위나 아래의 전구를 누르는 것 뿐입니다.

이 방법을 9개의 줄에 적용합니다.

이제 1~9번줄의 전구는 모두 꺼졌다는 명제는 자명합니다. 따라서 10번째 줄의 전구만이 켜져있을 가능성이 있습니다.

10번째 줄의 전구가 모두 꺼졌다면 모든 전구가 꺼져있는 상태입니다.

여기서 우리는 의문을 갖습니다.

위에서 생각한 방식을 그리디하게 적용하면 놓치는 케이스가 생기지 않을까?

네! 놓치는 경우가 생깁니다!

첫 번째 줄의 현재 상태에서만 그리디하게 진행하면 불을 다 끌수 있는데도 놓치는 경우가 생깁니다. 그렇다고 모든 전구에 대해 가능한 경우를 계산하면 2^100가지의 경우가.. 각 케이스마다 적용해야 하는 추가연산이 있는데 10억개의 경우는 너무 가혹합니다.

하지만, 위의 방식을 잘 생각해보면 첫 줄의 전구 상태에 따라 다음 작업들은 종속적으로 일어남을 알 수 있습니다.

따라서 우리가 찾아봐야 할 경우의 수는 첫번째 줄에서 일어날 수 있는 모든 경우인 2^10가지, 1024가지에 불과한것입니다.

1024가지 경우를 모두 돌려보는데엔 여러 방법이 있을텐데,

저는 개인적으로 비트마스킹 기법에 꽤나 익숙한 터라 해당 방법을 통해 구현했습니다.

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

public class Main {
	static int answer = Integer.MAX_VALUE;
	static int[][] delta = { { 0, 0 }, { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static boolean[][] testmap = new boolean[10][10];

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

		boolean[][] map = new boolean[10][10];

		for (int n = 0; n < 10; n++) {
			char[] line = br.readLine().toCharArray();
			for (int m = 0; m < 10; m++) {
				if (line[m] == 'O') {
					map[n][m] = true;
				}
			}
		}

		for (int i = 0; i < 1024; i++) {
			copy(map);
			int count = 0;

			for (int j = 0; j < 10; j++) {
				if (((1 << j) & i) != 0) {
					on(0, j);
					count++;
				}
			}

			for (int n = 0; n < 9; n++) {
				for (int m = 0; m < 10; m++) {
					if (testmap[n][m]) {
						on(n + 1, m);
						count++;
					}
				}
			}

			if (checkLight()) {
				answer = Math.min(answer, count);
			}
		}

		if (answer < Integer.MAX_VALUE) {
			System.out.println(answer);
		} else {
			System.out.println(-1);
		}
	}

	static boolean checkLight() {
		for (int i = 0; i < 10; i++) {
			if (testmap[9][i]) {
				return false;
			}
		}
		return true;
	}

	static void copy(boolean[][] map) {
		for (int i = 0; i < 10; i++) {
			testmap[i] = map[i].clone();
		}
	}

	static void on(int x, int y) {
		for (int i = 0; i < 5; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY)) {
				testmap[nX][nY] = !testmap[nX][nY];
			}
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x <= 9 && 0 <= y && y <= 9) {
			return true;
		}
		return false;
	}
}

감사합니다!!