백준 14939: 불 끄기

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

14939번: 불 끄기

 

코드

 

#include <iostream>
#include <string>
using namespace std;
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int ans[10], res = 1111111;
void dfs(int y, int x, int before, int now, int then, int cnt) {
    if (x == 10) {
        if (y == 0) dfs(y + 1, 0, now, then, 0, cnt);
        else {
            if (y == 9 and before == ans[y - 1] and now == ans[y]) res = min(res, cnt);
            if (before != ans[y - 1]) return;
            else dfs(y + 1, 0, now, then, 0, cnt);
        }
    }
    else {
        if (x == 0) dfs(y, x + 1, before ^ (1 << 0), now ^ ((1 << 0) + (1 << 1)), then ^ (1 << 0), cnt + 1);
        else if (x == 9) dfs(y, x + 1, before ^ (1 << 9), now ^ ((1 << 9) + (1 << 8)), then ^ (1 << 9), cnt + 1);
        else dfs(y, x + 1, before ^ (1 << x), now ^ ((1 << x) + (1 << (x - 1)) + (1 << (x + 1))), then ^ (1 << x), cnt + 1);
        dfs(y, x + 1, before, now, then, cnt);
    }
}
int main () {
    fastio();
    string s; 
    for (int i = 0; i < 10; i++) {
        cin >> s;
        for (int j = 0; j < 10; j++) ans[i] += s[j] == 'O' ? 1 << j : 0;
    }
    dfs(0, 0, 0, 0, 0, 0);
    cout << res;
}
 

풀이

전제:

       데카르트 좌표계를 y, x를 이용하여 나타낸다.

       전구의 줄은 같은 y좌표에 있는 전구들의 집합, 즉 같은 열에 있는 전구들을 의미한다.

       비트마스킹 값은 전구의 줄 상태를 나타낸다.

       이후 서술할 2번 구간에서 before, now, then은 전구의 위, 현재, 아래의 줄의 비트마스킹 값을 나타낸다.

       res는 최소한으로 눌러야 하는 스위치의 개수를 의미한다.

 

1.  입력을 비트마스킹으로 표현한다.

배열로 표현하는 것이 아닌 비트마스킹으로 표현함으로서 메모리 낭비 및 시간 복잡도를 줄일 수 있다.

 

2.  완전 탐색으로 표현함으로서, 모든 경우의 수를 점검할 수 있다.

2-1에서 before 값을 검사하는 것은, 현재 검사하는 전구는 위의 전구의 상태도 변환시킬 수 있기 때문이다.

2-2에서 then의 값도 변환시키는 것은 위와 비슷한 이유이다.

 

    2-1. x가 10일 때, 오른 쪽 끝에 도착했다는 것을 의미한다. 고로 y좌표를 1 더해준다. 그러나 y값이 9일 경우 재귀함수를 멈춘다.

          2-1-1. y가 0일 때는, before 값이 존재하지 않다. 고로 y좌표를 1 더해준다.

          2-1-2. y가 0이 아니다.

                2-1-2-1. y값이 9일경우, before값과 now값이 비트마스킹 값과 동일할 경우 res 값을 검사해준다.

                2-1-2-2. before 값이 비트마스킹 값과 동일하지 않을 경우 재귀함수를 멈춘다.

                2-1-2-2. before 값이 비트마스킹 값과 동일할 경우 y + 1을 한 재귀함수를 시작한다.

 

    2-2. x가 10이 아닐 때, 오른 쪽 끝에 도착하지 않았으므로 x좌표를 1 더해준다.

           2-2-1. x좌표가 0일 때, 스위치를 누른 전구와 위, 아래, 오른쪽 전구만 상태를 반전해주거나 

                 2-2-1-1. XOR연산으로 전구의 상태를 반전한다.

           2-2-2. x좌표가 9일 때, 스위치를 누른 전구와 위, 아래, 왼쪽 전구만 상태를 반전해준다.

           2-2-3. 그 이외의 상황에서는 스위치를 누른 전구 위, 아래, 왼, 오른쪽 전구의 상태를 반전해준다.