[백준/Baekjoon] 1799 비숍 C++ :: Back Tracking

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

1799번: 비숍

---

1. Logic

비숍이 움직일수 있는 특징은 검은색 칸은 흰색에 흰색은 검은색에 서로 영향을 주지 않는다. 그렇기 때문에 관점을 두개를 같이 보지말고 검은색은 검은색끼리 흰색은 흰색끼리 봐야한다.

 

이 특성을 이용하여 비숍을 놓기 위해서는 비숍을 놓을 위치의 대각선 방향에 다른 비숍이 있는지 없는지를 알고있어야 한다. N * N의 체스판에서 생기는 대각선의 갯수는 2N -1개이므로 N의 최대가 10이기 때문에 20개의 크기를 가진 배열 두개를 만들어 준다.  배열이 두개인 이유는 왼쪽 대각선(/)과 오른쪽 대각선(\) 두 방향 다 체크를 해줘야 하기 때문이다.

 

아래의 표를 보자.

(0,0) 에서 오른쪽 대각선(\)을 보면 col - row의 값이 전부 0으로 똑같은 것을 알 수 있다. 그렇기 때문에 rightDia[0] == 1이이면 비숍이 움직이는 구간의 오른쪽 대각선 방향 어딘가에 비숍이 놓여있다는 것을 알 수 있게 된다.

 

이번엔 (3,0)에서 왼쪽 대각선(/)을 보면 col + row의 값이 전부 3으로 똑같다. 그렇기 때문에 leftDia[3] == 1이면 동일 선상에 놓인 왼쪽 대각선 어딘가에 비숍이 놓여있다는 것을 알 수 있게 된다.

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

 

이러한 성질을 바탕으로 일반화 시킬 수 있다.

왼쪽 위에서 오른쪽 아래로 내려가는 대각선(\)을 구하는 식 : column - row  또는 (x - y)

왼쪽 아래에서 오른쪽 위로 올라가는 대각선(/)을 구하는 식 : column + row 또는 (x + y)

 

근데 여기서 / 대각선을 구할 때 왜 n -1을 해줬는지 궁금할 것이다. 

배은 arr[-1]같은 음수배열이 없기 때문에 column-row 를 해줬을 때 인덱스가 0부터 시작하도록 하기 위해 n-1(그래프에서 최대로 나오는 대각선의 갯수)을 해준 것이다.

예시로는 노란색체크표시가 있는 칸인 (4,2)를 보고 직접 계산해 보면 이해가 갈 것이다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int ans[2];
vector<vector<int>> chess(11, vector<int> (11, 0));
int leftDia[20]; //왼쪽 대각선(/)
int rightDia[20]; // 오른쪽 대각선(\)

void solve(int row, int col, int cnt, int color) {
    if(col >= n) {
        row++;
        //체스판은 검은색과 흰색판이 서로 번갈아가면서 나온다
        //항상 2씩 올려주기 때문에 짝수번재 1열에서 시작했으면 홀수 2열에서 시작했으면 짝수가 나온다
        if(col % 2 == 0) col = 1;
        else col = 0;
    }
    if(row >= n) {
        // 색깔별 최대 갯수를 갱신
        ans[color] = max(ans[color], cnt);
        return;
    }
	
    //비숍이 놓일수 있는 칸 && 왼쪽대각선에 비숍X && 오른쪽 대각선에 비숍X
    if(chess[row][col] && !leftDia[col - row + n - 1] && !rightDia[row + col]) {
        leftDia[col - row + n - 1] = rightDia[row + col] = 1;
        solve(row, col + 2, cnt+1, color);
        leftDia[col - row + n - 1] = rightDia[row + col] = 0;
    }
    solve(row, col+2, cnt, color);
}

int main() {
    ios_base::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 >> chess[i][j];
        }
    }

    //첫 시작을 1열에서 시작
    solve(0, 0, 0, 0);
    //첫 시작을 2열에서 시작
    solve(0, 1, 0, 1);

    cout << ans[0] + ans[1];
}

 

 

---

3. Feedback

생각하는데 시간도 많이 사용했지만 끝내 풀지 못했다,, 비숍의 특성은 떠올려서 서로 영향을 주지 않아 나눠서 생각하면 되겠다고 아이디어를 떠올렸지만 서로 영향을 주는 같은 색깔칸에 비숍이 위치했는지 확인하는 방법을 떠올리지 못해서 풀지 못했다.

 

230929 09:50 이해완료~~~~

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90