[Algorithm] Baekjoon 1799번 : 비숍

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

1799번: 비숍

int n;
int arr[11][11] = { 0 };
int dirSevenToOne[20] = { 0 }; // row + col
int dirFiveToEleven[20] = { 0 }; // col - row + N - 1
int answer[2] = { 0 };
 
 
 
void DFS(int row, int col, int count, int color)
{
    if (row >= n) // 넘어서면 종료.
    {
        answer[color] = max(answer[color], count);
        return;
    }
 
    if (col >= n)
    {
        if (col % 2 == 0) col = 1;
        else col = 0;
        ++row;
    }
 
    if (arr[row][col] == 1 && !dirSevenToOne[row + col] && !dirFiveToEleven[col - row + n - 1]) // 놓을 수 있으면 놓는다.
    {
        dirSevenToOne[row + col] = true;
        dirFiveToEleven[col - row + n - 1] = true;
 
        DFS(row, col + 2, count + 1, color);
 
        dirSevenToOne[row + col] = false;
        dirFiveToEleven[col - row + n - 1] = false;
    }
    
    DFS(row, col + 2, count, color); // 놓지않고 그냥 넘어간다.
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
    
    DFS(0, 0, 0, 0);
    DFS(0, 1, 0, 1);
 
    cout << answer[0] + answer[1];
}
 

N-Queen문제 비슷한건가? 해서 많이 생각해보다가, 도저히 모르겠어서 다른 풀이를 참고했다.

전혀.. 생각치도 못한 풀이방법이였고, 알고리즘 문제는 풀어도 풀어도 너무 무한한 세계같다.

 

먼저 비숍의 특징은 대각선으로만 이동이 가능하다.

이러한 특징때문에, 하얀칸과 검은색칸은 서로에게 영향이 가지 않는다는 규칙이 발생한다.

오직 같은색의 칸끼리만 서로 영향을 끼치기 때문에, 백트래킹을 두 색깔 따로 진행해서 합산한 결과를 출력한다.

같은 행에 대하여 col+2씩(같은 색 칸으로 건너뛰기) 수행하게 되는데, 같은 행에 대해서는 이전에 해당칸의 대각선에 비숍이 놓여져 있는게 아니면 비숍을 놓는게 가능하다.

 

여기서 해당칸의 대각선에 비숍이 놓여져있는지 확인하는 방법은 아래와 같다.

기본적으로 대각선은 두개로 나뉜다.

 

7시 < - > 1시방향 대각선 

5시 < - > 11시방향 대각선 

 

7시 <-> 1시방향 대각선의 특징으로는, 각 칸들의 row + col값이 같다는 것이다.

해당한 방향으로 이동할 때 행값이 증가하면 열값이 감소하고, 열값이 증가하면 행값이 감소하기 때문에 합산한 값이 항상 일정하다. 그렇기 때문에 배열의 인덱스로 사용이 가능하고, 그저 더하는 값이기 때문에 바로 배열 인덱스로 사용이 가능하다.

 

5시 <-> 11시방향 대각선의 특징으로는, 각 칸들의 col - row값 (혹은 row - col값)이 전부 동일하다는 특징이 있다.

왜냐하면 좌하단이나 우상단으로 이동하면은 각 행,열값이 동일하게(1씩) 감소 혹은 증가하기 때문이다.

여기서 배열인덱스로 쓰기위한 offset값인 N - 1을 추가로 더해줘서 인덱스로 사용하면 된다.

 

로직을 수행할 때, 해당 자리에 놓을 수 있는지 검사 후, 놓는것 외에도 그냥 넘어가는 경우의 수도 존재한다.

즉, 충분히 놓을 수 있음에도 그냥 넘어가는 것이다. 이래야 완전한 탐색이 된다.

해당 자리에 놓지 않고 그냥 넘어감으로써 아래 행을 검사할 때 오히려 추가적으로 비숍을 놓을 수 있는 경우의 수가 반드시 존재하기 때문에 '그냥 넘어간다..' 라는 행동도 반드시 추가해줘야 한다.

 

col >= n일 때 if (col % 2 == 0) col = 0; else col = 1;

이라는 코드가 있는 이유는 흰색이든 검은색이든 현재 각 행마다 시작위치가 0이였다가 1이였다가 바뀌기 때문에 col값이 체스판의 범위를 (n) 넘었을 때 2칸을 넘었는지 1칸을 넘었는지 체크를 통해 다음행에서의 출발위치가 결정된다.

이건 체스판을 보면 바로 알 수 있다.