C++[백준]14939번 불 끄기

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

14939번: 불 끄기

 

솔루션

---

대체 어떻게 푸는건지? 고민을 한참 하다 다른 블로그에 글을 보았다.

좋은아이디어로 접근 하는 방법을 찾을 수 있었는데,

 

dfs + 비트 마스킹으로 해결하는 방법이다.

 

타 블로그의 솔루션만 봤었기에, 풀이가 깔끔하지 않을 수 있다.

 

1) 먼저 0번째 행에 대해서 2^10가지의 경우를 다 해본다.

    - 불을 키거나(카운트 증가), 끄거나 (카운트 그대로) 둘 중 한가지의 경우다.

 2) 깊이가 10일 때, 각 열에 대해서 i(0<i<10)행 부터 i-1행에 불이 켜져 있다면 꺼 준다.

    - i-1행에 대해서는 i행 때 불을 건들 수 있는 위치로 유일하니, i행에서 꺼 주어야 한다.

    -  i행을 불을 다 껐을 때 i행에 불이 켜져 있는지 없는지는 확인하지 않는다. (i+1행에서 i행 불을 꺼 줄 것이기 때문.)

3) for문을 다 돌았을 때 마지막 9번째 행은 불이 다 꺼져 있어야 한다.

    - 9번째 행은 다음 행이 없으므로, 불을 꺼 줄 수 있는 장치가 없다.

4) 만약 마지막 행이 불이 다 꺼져 있다면 그 때 카운트를 리턴해 준다. 아니면 무한대를 리턴한다.

 

 

코드

---

#include <iostream>
#include<vector>
using namespace std;

char arr[102][102];
int dx[5] = { 1,0,-1,0,0 };
int dy[5] = { 0,1,0,-1,0 };


void turnSwitch(int x, int y) {
	
	for (int i = 0; i < 5; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];

		if (tx >= 0 && tx < 10 && ty >= 0 && ty < 10) {
			arr[tx][ty] == '#' ? arr[tx][ty] = 'O' : arr[tx][ty] = '#';
		}
	}
}
int calcTurnSwitch(int deep, int cnt) {
	if (deep == 10) {
		//계산
	
		vector<pair<int, int>> pos;
		for (int i = 1; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				if (arr[i - 1][j] == 'O') {
					turnSwitch(i, j);
					cnt++;
					pos.push_back({ i,j });
				}
			}
		}
		for (int i = 0; i < 10; i++) {
			arr[9][i] == 'O' ? cnt = 987654231 : cnt = cnt;
		}
		for (auto& p : pos) {
			turnSwitch(p.first, p.second);
		}
		return cnt;
	}
	else {
		int minCnt = 987654321;
		
		minCnt = min(minCnt, calcTurnSwitch(deep + 1, cnt));
		
		turnSwitch(0, deep);
		minCnt = min(minCnt, calcTurnSwitch(deep + 1, cnt + 1));
		turnSwitch(0, deep);
		return minCnt;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> arr[i][j];
		}
	}
	
	cout << calcTurnSwitch(0,0) << "\n";
}