https://www.acmicpc.net/problem/14939
14939호: 불을 꺼주세요
100개의 전구가 10×10 정사각형에 배열되어 있습니다.
전구의 스위치를 누르면 해당 전구의 상태와 위, 아래, 왼쪽, 오른쪽 전구도 바뀝니다.
100개의 전구 상태를 고려하여 모든 전구를 끕니다.
www.acmicpc.net
해결책
어떻게 해결합니까? 한참을 생각하다가 다른 블로그에서 글을 봤습니다.
좋은 생각으로 접근하는 방법을 찾을 수 있었고,
이것은 dfs + 비트 마스킹을 사용한 솔루션입니다.
다른 블로그에서만 솔루션을 보았으므로 솔루션이 명확하지 않을 수 있습니다.
1) 먼저 행 0에 대해 모든 2^10 경우를 시도합니다.
– 조명을 켜거나(카운트 증가) 끄거나(카운트는 동일하게 유지됨).
2) 깊이가 10일 때 i행의 조명을 끕니다(0
– 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";
}