백준 1779번 비숍

문제 링크 : https://www.acmicpc.net/problem/1799

처음에 문제를 풀고 제출을 했을 때 시간 초과가 났다.

나름 잘 푼것 같은데 시간초과가 나서 왜인지 고민하다가 다른사람들의 답을 보았는데

체스판 흑영역과 백영역을 구분해서 탐색하는 방법으로 시간을 줄여야 했던거였다.

아마 혼자서 그 방법을 생각하려면 굉장히 많은 시간이 들었을것같다.

그런데 흑백으로 구분해서 풀고나니 틀렸습니다가 떴다.

아무리 생각해도 로직이 잘못된것 없는것같아서 맞왜틀맞왜틀 하고있었는데 배열사이즈를 넉넉하게 잡아주었더니 맞았다.

문제 접근

1. 비숍은 이동방향이 대각선이므로 하나의 대각선에는 하나의 비숍만이 위치해야한다.

2. 오른쪽 위로 향하는 대각선을 기준으로 잡고 0부터 2n-2까지의 대각선(0부터 시각하였으므로 총 2n-1개의 대각선)을 재귀함수를 통해 완전탐색을 하며 하나의 대각선 마다 비숍의 자리를 골라주었다.

 비숍을 선택하지 않고 대각선을 넘기는 경우도 고려 해주었다.

 오른쪽 아래로 향하는 대각선과의 중복을 확인해주기 위해 비숍을 놓을 때 decr배열에 표시를 해주었고, 비숍을 놓기전에 decr배열을 보고 놓을수 있는지 없는지를 판단하였다.

3. 시간초과를 해결하기 위해 체스판 흑칸과 백칸에 놓을수 있는 비숍의 최대값을 각각 계산해주었고 마지막에 그 합을 출력하였다.

 흑칸, 백칸을 따로 구해주기 위해 재귀호출시 대각선을 한줄이 아닌 두줄을 건너뛰도록 하였다.

아래는 소스코드이다

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, maxR = 0;
int map[20][20];
bool decr[30];
 
void recur(int line, int picknum) {
    if (line >= 2 * n - 1) {
        maxR = max(maxR, picknum);
        return;
    }
 
    for (int y = 0; y <= line; y++) {
        int x = line - y;
        if (map[y][x] == 0 || decr[y - x + n - 1] == true) continue;
 
        decr[y - x + n - 1] = true;
        recur(line + 2, picknum + 1);
        decr[y - x + n - 1] = false;
    }
    recur(line + 2, picknum);
}
 
int main()
{
    int answer = 0;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    recur(0, 0);
    answer += maxR;
 
    maxR = 0;
    recur(1, 0);
    answer += maxR;
 
    cout << answer << endl;
}