개요
[문제링크](https://www.acmicpc.net/problem/14939)
각각의 칸에 전구가 들어있는 10x10 grid에서 어떤 칸의 스위치를 누르면 전구의 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태가 바뀔 때, 모든 전구를 끄기 위해 최소한으로 눌러야하는 스위치의 개수를 출력하는 문제이다.
문제 분석 및 풀이
우선 이 문제를 단순하게 DFS을 이용하여 Brute Force로 풀면 O(2^(N^2))의 시간복잡도를 가지게 된다(N은 행(=열)의 크기). 전구의 개수가 100개이므로 이렇게 되면 1초의 시간제한 내에 문제를 해결할 수 없음이 자명하다.
이를 위해 손으로 임의의 예시들을 차근차근 풀어보면 아래와 같은 규칙이 보인다.
- 같은 스위치를 두번 이상 누를 필요가 없다.
- 1. 의 성질을 이용하면, 스위치를 누르는 순서를 강제하여 중복을 방지할 수 있는데, 이때, 현재 위치를 (row, col)라고 할 때, (row-1,col)에 해당하는 칸의 전구가 켜져있다면, 현재 위치에서 스위치를 누르는 것 외에는 (row-1,col)의 전구를 다시 끌 수 있는 경우가 없으므로, 현재 위치에서 반드시 스위치를 눌러야만 한다.
위와 같은 규칙을 이용하면, (row-1,col) 위치에 대한 전구 상태 의존성이 없는 첫번째 행의 상태만 결정해 준 뒤, 두번째 행 이후로 자동으로 결정되는 스위치 조작 횟수를 세어주면 된다는 것을 알 수 있다. 또한, 마지막 시행이 끝난 후 [0,row-1] 범위의 전구는 모두 꺼져있는 것이 불변 조건이므로 마지막 행에 있는 모든 전구가 꺼져있는 것만 확인하면 된다.
이때, N = 10의 아주 작은 수임을 생각하여 각 열의 전구 상태를 10비트 Bitmask로 나타낼 수 있다.
이와같은 방식은 O(N^3)의 시간복잡도를 가지므로 제한시간 내에 충분히 해결 가능하다.
전체 코드
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int INF = 987654321;
void clickAction(vector<int> &grid, int p_row, int p_col)
{
for(int row = p_row - 1; row <= p_row + 1; ++row)
{
if(row >= 0 && row < 10)
{
if((grid[row] & (1<<p_col)) == 0)
grid[row] += 1<<p_col;
else
grid[row] -= 1<<p_col;
}
}
for(int col = p_col - 1; col <= p_col + 1; ++col)
{
if(col >= 0 && col < 10 && p_col != col)
{
if((grid[p_row] & (1<<col)) == 0)
grid[p_row] += 1<<col;
else
grid[p_row] -= 1<<col;
}
}
}
int count(vector<int> grid)
{
int ret = 0;
for(int row = 1; row < 10; ++row)
for(int col = 0; col < 10; ++col)
{
if(grid[row-1] & (1<<col))
{
ret++;
clickAction(grid, row, col);
}
}
for(int row = 0; row < 10; ++row)
if(grid[row] != 0) return INF;
return ret;
}
int firstLine(vector<int> grid, int col)
{
if(col == 10) return count(grid);
int ret = INF;
ret = min(ret,firstLine(grid, col + 1));
clickAction(grid, 0, col);
ret = min(ret, firstLine(grid, col + 1) + 1);
return ret;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
vector<int> grid(10, 0);
for(int i = 0; i < 10; ++i)
{
string s;
cin>>s;
for(int j = 0; j < 10; ++j)
if(s[j] == 'O')
grid[i] += (1<<j);
}
cout<<firstLine(grid, 0);
return 0;
}
제출결과
총평
한 점을 두번 이상 방문할 필요가 없다는 것을 이용해 한 점을 한번만 방문할 수 있도록 순서를 강제하여 반복문 불변식을 만들어 푸는 문제였다.
단순히 중복되는 연산을 찾아내어 풀어내는 Dynamic Programming 문제와 달리 논리적으로 필요가 없는 연산들을 배제하는 문제라 상당히 어려웠던 것 같다.
