[백준][1799번][백트레킹] 비숍

비숍

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

<문제>

#include <stdio.h>
 
int map[11][11];    // 처음 받아오는 값
int visit_a[30];    // 체크
int visit_b[30];
int Max = 0;
int chessSize;
 
 
void Black(int row, int cal, int cnt){
    if (cnt > Max)
        Max = cnt;
 
    
    if (cal > chessSize){
        row++;
 
        if (row % 2 == 0)
            cal = 2;
        else
            cal = 1;
    }
 
    if (row > chessSize){
        return;
    }
 
    if (visit_a[row + cal] == 0 && visit_b[10 + row - cal] == 0 && map[row][cal] == 1){
        visit_a[row + cal] =1;
        visit_b[10 + row - cal] = 1;
        Black(row, cal + 2, cnt+1);
        visit_a[row + cal] = 0;
        visit_b[10 + row - cal] = 0;
    }
    Black(row, cal + 2, cnt);
}
 
void White(int row, int cal, int cnt){
    if (cnt > Max)
        Max = cnt;
 
 
    if (cal > chessSize){
        row++;
 
        if (row % 2 == 0)
            cal = 1;
        else
            cal = 2;
    }
 
    if (row > chessSize){
        return;
    }
 
    if (visit_a[row + cal] == 0 && visit_b[10 + row - cal] == 0 && map[row][cal] == 1){
        visit_a[row + cal] = 1;
        visit_b[10 + row - cal] = 1;
        White(row, cal + 2, cnt + 1);
        visit_a[row + cal] = 0;
        visit_b[10 + row - cal] = 0;
    }
    White(row, cal + 2, cnt);
}
 
int main(void){
    int result;
    scanf("%d", &chessSize);
 
    for (int i = 1; i <= chessSize; i++)
        for (int j = 1; j <= chessSize; j++)
            scanf("%d", &map[i][j]);
 
    Black(1, 1, 0);    // 1,1 시작 에서 0번
    result = Max;
    Max = 0;
 
    White(1, 2, 0);
    result += Max;
 
    printf("%d\n", result);
 
    return 0;
}

<문제 푼 요령>

 1. 체스 판에서 비숍은 검정색 타일에 있는 녀석과 흰색 타일에 있는 녀석은 만날일이 없으므로 따로 검색해서 찾는다.

 2. 비숍을 놓는 경우와 놓지 않는 경우로 나누어서 재귀를 한다. 

 3. visit 배열 같은 경우는 두개로 나누어서 생각 할 수 있다. 비숍은 그 곳에 놓으면 대각선 타일에는 놓을 수 없다. 이 대각 선을 간단하게 표현해 줄 수 있는게 row+cal 이랑 mapsize(체스판 사이즈) + r ow- cal 로 나누어서 구별을 한다면 쉽게 대각선을 처리할 수 있다. 

 4. 그래서 각 타일당 가장 비숍을 많이 놓을 수 있는 경우를 출력해서 더하면 된다.