14927번 전구 끄기

참고 : https://blog.naver.com/pasdfq/221206211990

# 복습

# 문제

# 코테

# 코딩

# 비트마스크

# 브루트 포스

# 전구

# 조합

# bitmask

어려웠다.

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

시간 복잡도 : 2(on, off) ^ (n * n) = 2^(n*n)

Greedy + bitmask + 구현

1. 어떤 스위치를 2번 이상 누르는 것은 의미가 없다. 다시 되돌아가기 때문이다.

2. 첫 행(1행)에서 1 ~ n가지의 스위치 중 나올 수 있는 모든 경우의 수에 대하여 스위치를 누른다.

물론 이 때, on(1), off(0) 상관없이 누른다.

예)

1 2 3 4 5

가 있으면, -> (1), ..., (5), (1, 2), ...., (1, 2, 3, 4, 5)

3. 2번을 실행하였으면, 2 ~ N행에서는 바로 그 윗 행을 끌 수 있는 스위치가 있다면, 

그 스위치를 누른다. 

예)

x행에서 진행 중일 때는 x행이 아닌 (x-1)행에서 켜져 있는 상태인 스위치(1)를 꺼준다.(0)

4. 마지막 행(n)에서 전구가 모두 0이라면, 끌 수 있다.

5. 그게 아니라면, '-1'을 출력한다.

6. 첫 번째 행에서 앞으로 진행될 상황(경우)을 가정하고 진행하면, 

그 다음 행을 진행할 때부터는 경우의 수가 하나 밖에 없다.

이미 첫 번째 행에서 '상황' 자체를 가정했기 때문이다.

(어떤 스위치들을 눌러야할지에 대한 상황)

7. bitmask는 첫 번째 행에서 어떤 스위치(button)를 눌러야할지 구할 때, 사용한다.

게다가 빠르다. 아마 백트래킹 형식으로 구현했으면, SOF가 발생할지도 모른다.

첫 번째 코드 : 2차원 배열 활용

두 번째 코드 : 1차원 배열 활용

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 20
 
int n, board[Max][Max], temp[Max][Max], ans = INT32_MAX;
 
void Push(int y, int x)
{
    // 자신
    board[y][x] = abs(board[y][x] - 1);
 
    // 상
    if (y >= 1) board[y - 1][x] = abs(board[y - 1][x] - 1);
 
    // 하
    if (y < n - 1) board[y + 1][x] = abs(board[y + 1][x] - 1);
 
    // 좌
    if (x >= 1) board[y][x - 1] = abs(board[y][x - 1] - 1);
 
    // 우
    if (x < n - 1) board[y][x + 1] = abs(board[y][x + 1] - 1);
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &temp[i][j]);
        }
    }
 
    // 0부터 시작해야하니, (1 << n) - 1까지 진행
    for (int button = 0; button < (1 << n); button++) {
        // button은 어떤 버튼을 눌러야 할지 알려준다.
        // 1이면 그 버튼을 누른다.
 
        // 복사
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = temp[i][j];
            }
        }
        
        int cnt = 0; // 누르는 횟수
        
        // 첫 행(0) : 이제 어떤(i) 버튼을 눌러야 할지 구해보자. 
        for (int i = 0; i < n; i++) {
            if (button & (1 << i)) {
                // button에 (1 << i)가 포함되어 있다면
                // i번째 버튼의 상태를 바꿔준다.
                Push(0, i);
                ++cnt;
            }
        }
 
        // 이후의 행(1 ~ n-1)
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i - 1][j]) {
                    Push(i, j);
                    ++cnt;
                }
            }
        }
 
        bool stop = false;
 
        // 마지막 행이 0인지 아닌지 검사
        for (int j = 0; j < n; j++) {
            if (board[n - 1][j]) {
                stop = true;
                break;
            }
        }
 
        if (!stop) ans = min(ans, cnt);
    }
 
    printf("%d\n", ans == INT32_MAX ? -1 : ans);
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 20
 
int n, board[Max], temp[Max], ans = INT32_MAX;
 
void Push(int y, int x)
{
    board[y] ^= 1 << (n - x - 1); // 자신
    if (y) board[y - 1] ^= 1 << (n - x - 1); // 상
    if (y != n - 1) board[y + 1] ^= 1 << (n - x - 1); // 하
    if (x) board[y] ^= 1 << (n - x); // 좌
    if (x != n - 1) board[y] ^= 1 << (n - x - 2); // 우
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
 
    int input;
 
    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j >= 0; j--) {
            scanf("%d", &input);
            if (input) temp[i] |= 1 << j;
        }
    }
 
    //0부터 시작해야하니, (1 << n) - 1까지 진행
    for (int button = 0; button < (1 << n); button++) {
        // button은 어떤 버튼을 눌러야 할지 알려준다.
        // 1이면 그 버튼을 누른다.
 
        // 복사
        for (int i = 0; i < n; i++) {
            board[i] = temp[i];
        }
 
        int cnt = 0; // 누르는 횟수
 
        // 첫 행(0) : 이제 어떤(i) 버튼을 눌러야 할지 구해보자. 
        for (int i = 0; i < n; i++) {
            if (button & (1 << (n - i - 1))) {
                // button에 (1 << i)가 포함되어 있다면
                // i번째 버튼의 상태를 바꿔준다.
                Push(0, i);
                ++cnt;
            }
        }
 
        // 이후의 행(1 ~ n-1)
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i - 1] & (1 << (n - j - 1))) {
                    Push(i, j);
                    ++cnt;
                }
            }
        }
 
        if (!board[n - 1]) {
            ans = min(ans, cnt);
        }
    }
 
    printf("%d\n", ans == INT32_MAX ? -1 : ans);
 
    return 0;
}