본문 바로가기

백준

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

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

 

14939번: 불 끄기

전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄

www.acmicpc.net

 

솔루션


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

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

 

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";
}

'백준' 카테고리의 다른 글

C++[백준]3006번 터보소트  (0) 2023.04.18
C++[백준]12873번 기념품  (0) 2023.04.18
C++[백준]9527번 1의 개수 세기  (2) 2023.04.13
C++[백준]16724번 피리부는 사나이  (0) 2023.04.13
C++[백준]2162번 선분 그룹  (0) 2023.04.13