[C/C++] BOJ 1799 :: 비숍

BOJ 1799 :: 비숍

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

문제 풀이

두 방향의 대각선에 비숍이 놓여져 있는지 확인하면서 처음부터 끝까지 찾는 일반적인 방법으로는 계속 시간초과가 났다.

3시간 동안 생각해보았지만 ㅠㅠ 시간을 줄일 수 있는 방법을 알아내지 못하여 다른 사람들의 코드를 참고해 풀기로 하였다..

내가 참고한 블로그 :  http://wookje.dance/2017/11/01/boj-1799-%EB%B9%84%EC%88%8D/

★ 체스판을 두 경우로 나누어 푸는 것이 핵심적인 방법이다!

비숍의 경우, 검은색 칸과 흰색 칸은 각자의 비숍을 놓을 수 있는 자리에 영향을 주지 않는다.

검은색 칸은 검은색 칸끼리만 영향을 받고 흰색 칸은 흰색 칸끼리만 영향을 받는다.

따라서 검은색 칸과 흰색 칸, 두 가지의 경우로 나누어 풀면 시간을 줄일 수 있다.

최대 10*10 만큼 탐색해야 하는 것을 5*5 두 번으로 탐색 가능하다.

비숍을 칸에 놓을 수 있는 경우의 수 : 놓는다 / 놓지 않는다 => 2가지

비숍을 놓을 수 있는 칸의 수 : 2 * N/2 * N/2

시간복잡도는 O(2^(N/2*N/2)) 가 된다!

<예시>

○ : 비숍을 놓을 수 있는 칸

● : 비숍이 놓인 칸

○	○		○	○
	○
○		○		○
○
○		○	○	○

1) 검은색의 경우 놓을 수 있는 최대 비숍의 개수

●				●
	○
●		○		●
○		○		○

2) 흰색의 경우 놓을 수 있는 최대 비숍의 개수

	●		●
○
			●

3) 전체

●	●		●	●
●				●
			●

최대 7개의 비숍을 놓을 수 있다.

★ 현재 위치에 비숍을 놓을 수 있는 지를 판단하기 위해 3가지 조건을 고려해야 한다.

if (chess[row][col] && !l[col - row + N - 1] && !r[row + col])

1) chess판에 비숍을 놓을 수 있는가.

2) ▨ 방향에 비숍이 놓여져 있는가. ( l 배열로 표현)

3) ▧ 방향에 비숍이 놓여져 있는가.  ( r 배열로 표현)

(0,0)				(0,4)
	(1,1)		(1,3)
		(2,2)
	(3,1)		(3,3)
(4,0)				(4,4)

(2,2)를 기준으로 보았을 때,

▧ 방향은 col-row의 값이 같다.

▨ 방향은 row+col의 값이 같다.

▧ 방향은 col-row를 했을 때, 음수가 나올 수 있으므로 index 0 부터 시작하도록 하기 위해 N-1을 해 주었다.

검은색 칸, 흰색 칸끼리만 고려해 주기 위하여 col+2를 해가면서 탐색한다.

★ 다음 행으로 넘어갈 때, col이 짝수이면,  col = 1 을 해준다.

(짝수열을 갖는 행의 다음 행은 홀수열을 갖는 행이다.)

★ col이 홀수이면, col = 0을 해준다.

(홀수열을 갖는 행의 다음 행은 짝수열을 갖는 행이다.)

 if (col >= N) {

        row++;

        if(col%2 == 0) col = 1;

        else col = 0;

    }

★ 그 자리에 비숍을 놓을 수 있어도 놓지 않고 다음으로 넘어가는 경우가 있기 때문에

if-else문이 아니라 if문으로 하여 무조건 다음으로 넘어가는 경우를 고려해 주도록 한다.

 if (chess[row][col] && !l[col - row + N - 1] && !r[row + col])

    {

        l[col - row + N - 1] = r[row + col] = 1;

        tracking(row, col+2, count + 1, color);

        l[col - row + N - 1] = r[row + col] = 0;

    }

    tracking(row, col+2, count, color);

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1799/BOJ_1799.cpp

// 백준알고리즘 1799번 :: 비숍
#include<iostream>
#define max(a,b) a > b ? a : b
using namespace std;
 
int N;
int ans[2];
int chess[11][11];
int l[20];
int r[20];
 
// 놓을 수 있는 비숍의 최대개수를 구하는 함수
// 흑/백, 두 가지 경우로 나누어 계산
 
void tracking(int row, int col, int count, int color)
{
    if (col >= N) {
        row++;
        if(col%2 == 0) col = 1;
        else col = 0;
    }
    if (row >= N) {
        ans[color] = max(ans[color], count);
        return;
    }
 
    if (chess[row][col] && !l[col - row + N - 1] && !r[row + col])
    {
        l[col - row + N - 1] = r[row + col] = 1;
        tracking(row, col+2, count + 1, color);
        l[col - row + N - 1] = r[row + col] = 0;
    }
    tracking(row, col+2, count, color);
}
 
int main(void)
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> chess[i][j];
        }
    }
 
    tracking(0, 0, 0, 0);
    tracking(0, 1, 0, 1);
 
    cout << ans[0] + ans[1];
 
    return 0;
}