[BOJ] 14939 불 끄기 (C/C++)

14939번: 불 끄기

문제

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라

입력

10줄에 10글자씩 입력이 주어진다. #은 꺼진 전구고 O(대문자 알파벳 o)는 켜진 전구다. #과 O외에는 입력으로 주어지지 않는다.

출력

모든 전구를 끄기 위해 최소한으로 눌러야 하는 스위치의 개수를 출력하라. 불가능하면 -1를 출력하라.

---

오랜만에 그리디 문제를 풀었다. 그리디는 처음 배울 때에는 세상 만만해보이는데 막상 문제를 풀다보면 그 순간 순간에 어떤 행동이 최적인지 알아내는게 생각보다 어렵다. 심지어 이건 세상 만만한 완전 탐색도 끼어있음에도 그리 쉽지 않았다.

 

문제의 핵심은

1. 최소로 누르는 경우엔 뭘 먼저 누르던지 상관없음. 즉 순서는 상관없으므로 위에서부터 처리해나가면 된다.

2. 지금 (i, j) 번째 전구를 보고 있는 상황에서는 그 위의 전구가 켜져있는지를 궁금해한다. 위에서 아래로 내려가기 때문에 (i-1, j) 전구가 켜져있으면 지금밖에 끌 수 있는 기회가 없음. 따라서 첫 줄 전구의 상태만 어떻게 한다면 그 이후로는 그냥 내려가기만 하면 된다.

 

첫 줄 전구 상태를 정하기 위해서 비트마스킹을 사용했다. 전구가 10개밖에 되지 않기 때문에 2^10은 해봤자 1024다. 다른 문제를 풀면서도 비트마스킹 생각을 하긴하는데 숫자가 크면 막 2^100 이렇게 되어버리니까 아무데나 적용할 수 없었다. 그래도 이 문제는 10밖에 되지 않는다.

 

각 케이스마다 원상 복구, 모든 전구가 꺼졌는 지 검사하는걸 이중 for문을 사용해서 할 수도 있었지만, memcpy, memcmp 함수를 한번 사용해봤다. 이게 더 빠를지 아닐 지는 모르겠지만 코드가 깔끔해지긴 했다. 대신 이 함수들은 사용할 때 크기를 잘 정해줘야 된다. 아니면 어떤 문제가 생길 지 모른다.

 

	#include <iostream>
	#include <algorithm>
	#include <string.h>
	#define MAX 1000
	using namespace std;
	bool input[10][10]; bool state[10][10]; bool check[10][10];
	int next_x[4] = { -1, 0, 1, 0 };
	int next_y[4] = { 0, 1, 0, -1 };
	int ans = MAX;
	bool checkBound(int x, int y) {
	return x >= 0 && x < 10 && y >= 0 && y < 10;
	}
	void Click(int x, int y) {
	state[x][y] = !state[x][y];
	for (int dir = 0; dir < 4; dir++) {
	int nx = x + next_x[dir];
	int ny = y + next_y[dir];
	if (checkBound(nx, ny)) {
	state[nx][ny] = !state[nx][ny];
	}
	}
	}
	int simulation() {
	int cnt = 0;
	for (int i = 1; i < 10; i++) {
	for (int j = 0; j < 10; j++) {
	if (state[i - 1][j]) {
	cnt++;
	Click(i, j);
	}
	}
	}
	if(!memcmp(state, check, sizeof(state)))
	return cnt;
	return MAX;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	char c;
	for (int i = 0; i < 10; i++) {
	for (int j = 0; j < 10; j++) {
	cin >> c;
	if (c == 'O')
	input[i][j] = true;
	}
	}
	for (int s = 0; s < (1 << 10); s++) {
	memcpy(state, input, sizeof(input));
	int cnt = 0;
	for (int i = 0; i < 10; i++) {
	if (s & (1 << i)) {
	cnt++;
	Click(0, i);
	}
	}
	cnt += simulation();
	ans = min(ans, cnt);
	}
	if (ans >= MAX) cout << "-1\n";
	else cout << ans << '\n';
	return 0;
	}

view raw 14939.cpp hosted with ❤ by GitHub

 

후기)

오늘 코로나가 의심돼서 PCR 검사를 받고 왔다. 막 아픈건 아닌데 컨디션이 좋지는 않다. 내일 아침에 결과 나온다니 기다려봐야지.