1799번

1799번 - 비숍

처음에는 N-Queen 처럼 행으로 접근했더니 시간 초과가 발생.

그 다음에는 대각선으로 생각했으나, 시간 초과 발생.

그리고 다른 사람들 힌트를 생각했더니, 홀수번째 대각선과 짝수번째 대각선은 서로에게 영향을 미치지 않는다.

그렇기 때문에 합으로 나타내서 시간을 줄일 수 있었다.( 예를들면 1억x1억을 1억+1억으로 바꾸면 시간이 확 줄듯이)

그렇게 해서 오른쪽 위로 올라가는 대각선을 짝수번째와 홀수번째로 나누었다.

처음 dfs문에서 x,y,c를 구하는 것은 각 대각선의 첫번째 값을 구하는 방법이다.

그리고 while문을 통해서 대각선의 값들을 하나씩 넣어보는 방식으로 문제를 풀었다.

이때 chk 배열은 대각선과 직각을 이루는 대각선이 사용됐는지 여부를 판단하는데 사용했다.

즉, 처음에는 ↗ 대각선을 타고 가면서, 비숍을 놓을 수 있으면 그 자리에서 ↘ 을 사용했다고 체크한다. (그 값이 c)

###

dfs에서 전역변수를 통해서 최대값을 구하는 방식말고, return 값을 이용해서 최대값을 구하는 방식을 생각해볼 것.

오른쪽 상단으로 향하는 대각선에 포함되는 좌표들의 특징=> x+y 가 일정하다 

오른쪽 하단으로 향하는 대각선에 포함되는 좌표들의 특징=> y-x 가 일정하다.

이런 스킬을 이용한 문제풀이 => http://wookje.dance/2017/11/01/boj-1799-%EB%B9%84%EC%88%8D/

<정답 코드>

#include<iostream>
 
using namespace std;
int n, ans;
int map[10][10];
bool chk[2][21];
int sum[2] = { -1,-1 };
int dfs(int k,int d,int s)
{
 
    if (k >= 2 * n - 1)
    {
        if (sum[d] < s)
        {
            sum[d] = s;
        }
 
        return sum[d];
    }
 
    int x, y, c;
    if (k >= n)
    {
        x = n - 1;
        y = k - n + 1;
        c = y - x + n;
    }
    else
    {
        x = k;
        y = 0;
        c = y - x + n;
    }
 
    while (x >= 0 && y >= 0 && x < n && y < n)
    {
        if (map[x][y] == 1 && !chk[d][c])
        {
            chk[d][c] = true;
            dfs(k + 2, d, s+1);
            chk[d][c] = false;
        }
        x -= 1;
        y += 1;
        c = y - x + n;
    }
 
    dfs(k + 2, d, s);
 
    return sum[d];
}
int main()
{
    //freopen("input.txt", "r", stdin);
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }
 
    ans=dfs(0,0,0)+dfs(1,1,0);
 
    cout << ans << "\n";
 
    return 0;
}