[BOJ] 백준 1799 비숍

문제 링크

www.acmicpc.net/problem/1799

1799번: 비숍

 

풀이

1) 백트래킹을 해야 합니다. 근데 나이브하게 탐색하면 당연히 시간 초과입니다.

 

2) 우선 어떤 칸의 행, 열로 그 칸이 어떤 대각선에 속해있는지 $O(1)$로 체크할 수 있습니다.

행, 열을 $i, j$라 할 때 오른쪽 위로 가는 대각선을 보면 $(i + j)$값이 같은 칸들이 같은 대각선에 속하고, 오른쪽 아래로 가는 대각선을 보면 $(i - j)$값이 같은 칸들이 같은 대각선에 속합니다. 

다만 $(i - j)$는 음수가 될 수 있으므로 $n$을 더해 양수로 만들어줍시다.

 

 

3) 대각선 체크를 $O(1)$로 할 수 있다고 해도 모든 칸을 가로, 세로 순으로 탐색하면 경우의 수가 너무 많아집니다.

체스판을 45$^{\circ}$ 기울였다고 생각하면 대각선 순으로 탐색할 수 있습니다. 그러면 한 줄 당 하나의 칸만 선택해주면 됩니다. 이를 코드의 40번째 줄에서 처리합니다.

 

4) 이까지 했으면 백트래킹 하는 경우의 수가 $O((N!)^{2})$ 정도로 줄어들게 됩니다. 하지만 아직도 많습니다.

사실 체스판을 잘 보면, 짝수번째 대각선과 홀수번째 대각선이 독립적이라는 걸 알 수 있습니다. 즉, 짝수번 대각선에 있는 비숍은 홀수번 대각선의 비숍을 절대 잡을 수 없습니다.

 

따라서 짝수번, 홀수번 대각선을 각각 백트래킹 해주면$O(N!)$ 정도로 충분히 통과할 수 있게 됩니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
using namespace std;
using pii = pair<int, int>;

int n;
bool chk[22];
vector<vector<pii>> p;

int go(int i) {
    if (i >= p.size()) return 0;

    int ret = 0;
    for (int j = 0; j < p[i].size(); j++) {
        auto[x, y] = p[i][j];
        if (!chk[x - y + n]) {
            chk[x - y + n] = true;
            ret = max(ret, go(i + 2) + 1);
            chk[x - y + n] = false;
        }
    }
    ret = max(ret, go(i + 2));

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    p.resize(2 * n + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            if (x == 1) p[i + j].emplace_back(i, j);
        }
    }
    cout << go(0) + go(1);
}