[BOJ] 1799 : 비숍

문제 링크

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

1799번: 비숍

백트래킹에 관한 문제다.

풀이

처음 문제를 읽었을 때 왜 이게 골드1 난이도의 문제일까? 라는 의문이 들었다. 비숍이 들어갈 위치는 정해져있고 거기에 비숍이

1. 놓이거나

2. 안놓이거나 둘 중 하나다.

비숍이 놓일 수 있는 모든 위치를 벡터에 저장한 뒤 그 위치를 백트래킹으로 모두 돌면서 depth가 비숍이 놓일 수 있는 모든 칸의 개수와 같아지면 그때 체스판에 놓여있는 체스의 개수 중 최대값을 출력하면 되겠구나 라고 생각했다. 시간도 10초면 넉넉한 편이니 바로 코드를 짰다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N;
const int MAX_N = 10 + 3;
int chess[MAX_N][MAX_N];
vector<pair<int,int>> cango; // 비숍이 놓일 수 있는 위치
int MAX;
bool is_ok(int y, int x) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (chess[i][j] == 2) {
                if (abs(i - y) == abs(j - x))
                    return false;
            }
        }
    }
    return true;
}
 
void backtracking(int depth, int B) {
    if (depth == cango.size()) {
        MAX = max(MAX, B);
        return;
    }
    if (is_ok(cango[depth].first, cango[depth].second)) { //다음칸을 갈 수 있으면
        chess[cango[depth].first][cango[depth].second]++;
        backtracking(depth + 1, B + 1);
        chess[cango[depth].first][cango[depth].second]--;
    }
    backtracking(depth + 1, B);
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> chess[i][j];
            if (chess[i][j])
                cango.push_back({ i,j });
        }
    }
    backtracking(0, 0);
    cout << MAX << "\n";
    return 0;
}
 
 

물론 예제가 맞아서 제출했는데 그대로 시간초과. 이 방법이 외엔 딱히 떠오르는 방법이 없었다. 1시간 넘게 고민했지만 결국 욱제님의 블로그를 참고했다.

체스의 특성을 이용해서 검은색 칸과 흰색 칸을 나눠서 생각하면 시간을 단축할 수 있다. 왜냐 검정 칸과 흰 칸은 서로 절대 같은 대각선에 있을 수 없다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <climits>
#include <algorithm>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
int N;
const int MAX_N = 10 + 3;
int chess[MAX_N][MAX_N];
vector<pair<int, int>> cango[2];
stack<pair<int, int>> bishop[2];
int MAX[2];
 
bool is_ok(int y, int x, int depth, int black_white) {
    stack<pair<int, int>> S(bishop[black_white]);
    while (!S.empty()) {
        int temp_y = S.top().first;
        int temp_x = S.top().second;
        S.pop();
        if (abs(y - temp_y) == abs(x - temp_x))
            return false;
    }
    return true;
}
//void show_chess() {
//    for (int i = 0; i < N; i++) {
//        for (int j = 0; j < N; j++) {
//            cout << chess[i][j] << " ";
//        }
//        cout << "\n";
//    }
//}
 
void backtracking(int depth, int B, int black_white) {
    if (depth == cango[black_white].size()) {
        MAX[black_white] = max(MAX[black_white], B);
        return;
    }
    if (is_ok(cango[black_white][depth].first, cango[black_white][depth].second, depth, black_white)) { //다음칸을 갈 수 있으면
        chess[cango[black_white][depth].first][cango[black_white][depth].second]++;
        bishop[black_white].push({cango[black_white][depth].first, cango[black_white][depth].second});
        backtracking(depth + 1, B + 1, black_white);
        bishop[black_white].pop();
        chess[cango[black_white][depth].first][cango[black_white][depth].second]--;
    }
    backtracking(depth + 1, B, black_white);
}
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> chess[i][j];
            if (chess[i][j]) {
                if (i % 2 == 0 && j % 2 == 0)
                    cango[0].push_back({ i,j });
                else if (i % 2 == 1 && j % 2 == 1)
                    cango[0].push_back({ i,j });
                else cango[1].push_back({ i,j });
            }
        }
    }
    backtracking(0, 0, 0);
    backtracking(0, 0, 1);
    cout << MAX[0] + MAX[1] << "\n";
    return 0;
}
 
 

그렇게 기존 코드에서 급하게 코드를 바꿔 제출해서 AC를 받았다.

처음 코드의 시간복잡도는 2 * N * N (2는 백트래킹에서 비숍을 놓냐 안놓냐)

반반 나눠서 한 코드의 시간복잡도는 2* N/2 * N/2 로 훨씬 더 줄어들었다.

체스판의 특성을 활용하는 센스가 필요했던 문제다.