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 |