백준 1799 비숍

😞 어려워

문제

서로를 잡을 수 없게 비숍을 놓을 때, 비숍 개수의 최댓값을 구하라.

풀이

시간 초과

무식하게 다돌리는 풀이로 시간복잡도는 $O(2^{10*10})$ 이다.

하지만 내 풀이는 아마 이것보다 더 많이 들었을 것이다. 왜냐면 caught 체크할때 다시 다봤기 때문에 시간복잡도는 이정도 $O(2^{10*10} \times 10)$ .

#include <iostream>

using namespace std;

int board[11][11], n;
int dr[] = {0, 0, -1, 1}, dc[] = {1, -1, 0, 0};
int ret = 0;

bool isRange(int r, int c) {
    return r>=0 && r<n && c>=0 && c<n;
}

bool isCaught(int r, int c, int dir) {
    int rr[] = {1, -1, 1, -1}, cc[] = {1, 1, -1, -1};
    int tr = r, tc = c;
    while(isRange(tr, tc)) {
        if(board[tr][tc]==2)
            return true;
        tr += rr[dir];
        tc += cc[dir];
    }
    return false;
}

bool isCaught(int r, int c) {
    for (int i=0; i<4; ++i) {
        if(isCaught(r, c, i))
            return true;
    }
    return false;
}

// 그냥 다 놔보면 되지 않을까
void solve(int r, int c, int cnt) {
    for (int i=r; i<n; ++i) {
        int cc = 0;
        if(i==r+1)
            cc = c+1;
        for(int j=cc; j<n; ++j) {
            if(board[i][j] == 0 || board[i][j] == 2)
                continue;
            if(isCaught(i, j))
                continue;
            board[i][j] = 2;
            solve(i, j, cnt+1);
            board[i][j] = 1;
        }
    }
    ret = max(ret, cnt);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            cin>>board[i][j];
        }
    }
    solve(0, 0, 0);
    cout << ret;
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

나누어서 푼다

두 부분으로 쪼개서 시간복잡도를 줄이는 방법. 이제까지 많이 봤던 방법인데 생각하지 못했어 😢

체스판에서 하얀부분과 검은부분의 비숍이 절대 서로를 잡지 못한다는 것에 기반해서 두 부분으로 나누어 풀 수 있다. 이 경우 $O(2^{5*5})$

게다가 caught 체크할 때 그 대각선에 못 온다는 정보만 기록해 놓으면 $O(1)$ 에 체크하기 때문에 진짜로 $O(2^{5*5})$ 이다.

좋았던 풀이 기법

대각선 체크
- / 형태의 대각선은 같은 대각선이라면 r+c 가 같다.
- \ 형태의 대각선은 같은 대각선이라면 c-r 이 같다.
c-r 이 음수일수도 있기 때문에 n-1 을 더해서 양수로 만들어주자.
$\rightarrow$ 방향으로 검사하기

그냥 순서대로 검사를 한다. 뭔가 단순한데 생각하기 힘들다.

#include <iostream>

using namespace std;

int board[11][11], n, total = 0;
int diag1[22], diag2[22];
int ret[2];

void solve(int r, int c, int cnt, bool flag) {
    if (c >= n) {
        r++;
        c%2==0? c=1 : c=0;
    }
    if (r >= n) {
        ret[flag] = max(ret[flag], cnt);
        return;
    }
    if (board[r][c] && !diag1[c - r + n - 1] && !diag2[r + c]) {
        diag1[c - r + n - 1] = diag2[r + c] = 1;
        solve(r, c + 2, cnt + 1, flag);
        diag1[c - r + n - 1] = diag2[r + c] = 0;
    }
    solve(r, c+2, cnt, flag);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> board[i][j];
        }
    }
    solve(0, 0, 0, 0);
    solve(0, 1, 0, 1);
    cout << ret[0] + ret[1];
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

Written by@[jungin]

안녕하세요

GitHub