[백준 1799] 비숍 - C++ / 백트래킹

문제

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

1799번: 비숍

나의 코드 - 시간초과

#include <iostream>
#define MAX 10
 
using namespace std;
 
bool chess[MAX][MAX];
bool visited1[MAX * 2]; //오른쪽에서 왼쪽으로 가는 대각선
bool visited2[MAX * 2]; //왼쪽에서 오른쪽으로 가는 대각선
int bishop;
int chess_size;
 
void DFS(int cnt, int xi, int yi) {
    for (int y = yi; y < chess_size; y++) {
        for (int x = 0; x < chess_size; x++) {
            if (!chess[y][x] && visited1[x + y + 1] && visited2[x - y + chess_size]) continue;
            visited1[x + y + 1] = true;
            visited2[x - y + chess_size] = true;
            DFS(cnt + 1, x + 1, y);
            visited1[x + y + 1] = false;
            visited2[x - y + chess_size] = false;
        }
    }
 
    if(cnt > bishop)
        bishop = cnt;
    return;
}
 
int main(void) {
    cin >> chess_size;
 
    for (int i = 0; i < chess_size; i++)
        for (int j = 0; j < chess_size; j++)
            cin >> chess[i][j];
    
    DFS(0, 0, 0);
 
    cout << bishop << '\n';
}

**문제점**

시간초과도 문제지만 일단 재귀함수로 돌아가는데 x좌표가 말썽이다.

x가 4인데도 불구하고 y만 커져서 x=0으로 초기화 안되고 이상하게 돌아간다.

그래서 그냥 x=0으로 for문 돌리는데 이건 dfs라고 할 수 없다(재귀로 들어가면서 이전 자신보다 더 깊게 들어가야한다)

이 코드는 여러곳에서 문제가 발생한다. 그래서 for문 없이 재귀함수로만 구현을 시도한다.

#include <iostream>
#define MAX 10
 
using namespace std;
 
bool chess[MAX][MAX];
bool visited1[MAX * 2]; //오른쪽에서 왼쪽으로 가는 대각선
bool visited2[MAX * 2]; //왼쪽에서 오른쪽으로 가는 대각선
int bishop;
int chess_size;
 
//for문없이 재귀함수만으로 구현하기
void DFS(int cnt, int x, int y) {
    if (x >= chess_size) {
        x = 0;
        y++;
    }
    if (y >= chess_size) {
        if (cnt > bishop)
            bishop = cnt;
        return;
    }
 
    if (chess[y][x] && !visited1[x + y + 1] && !visited2[x - y + chess_size]) {
        visited1[x + y + 1] = true;
        visited2[x - y + chess_size] = true;
        DFS(cnt + 1, x + 1, y);
        visited1[x + y + 1] = false;
        visited2[x - y + chess_size] = false;
    }
    DFS(cnt, x + 1, y);
}
 
int main(void) {
    cin >> chess_size;
 
    for (int i = 0; i < chess_size; i++)
        for (int j = 0; j < chess_size; j++)
            cin >> chess[i][j];
    
    DFS(0, 0, 0);
 
    cout << bishop << '\n';
}

 

하지만 이렇게 풀어도 시간초과는 발생한다.

이제는 다른 사람의 아이디어를 빌려야하는 차례가 왔다 ㅠㅠㅠㅠ

 

백준풀이

코드 참조 : https://j2wooooo.tistory.com/80

검은색 체스칸과 흰색 체스칸은 서로 절대로 공격할 일이 없다!!!!

#include <iostream>
#define MAX 10
 
using namespace std;
 
bool chess[MAX][MAX];
bool visited1[MAX * 2]; //오른쪽에서 왼쪽으로 가는 대각선
bool visited2[MAX * 2]; //왼쪽에서 오른쪽으로 가는 대각선
int bishop[2];
int chess_size;
 
//for문없이 재귀함수만으로 구현하기
// color == 0 : 검은색, color == 1 : 흰색
void DFS(int cnt, int x, int y, int color) {
    if (x >= chess_size) {
        y++;
        if (x % 2 == 0) x = 1;
        else x = 0;
    }
    if (y >= chess_size) {
        if (cnt > bishop[color])
            bishop[color] = cnt;
        return;
    }
 
    if (chess[y][x] && !visited1[x + y + 1] && !visited2[x - y + chess_size]) {
        visited1[x + y + 1] = true;
        visited2[x - y + chess_size] = true;
        DFS(cnt + 1, x + 2, y, color);
        visited1[x + y + 1] = false;
        visited2[x - y + chess_size] = false;
    }
    DFS(cnt, x + 2, y, color);
}
 
int main(void) {
    cin >> chess_size;
 
    for (int i = 0; i < chess_size; i++)
        for (int j = 0; j < chess_size; j++)
            cin >> chess[i][j];
    
    DFS(0, 0, 0, 0); //검은색 체스판
    DFS(0, 1, 0, 1); //흰색 체스판
 
    cout << bishop[0] + bishop[1] << '\n';
}

 

1. x가 2칸씩 건너간다.

2. 검은색과 흰색을 따로 경우의 수로 해서 분리하고 이에 대한 결과를 합해서 출력한다.

3. 다음줄로 넘어갈 때 x가 0인지 1인지 갈린다. (이것이 중요!!!!!!)

 

대체 이러한 아이디어는 어떻게 떠오르는 것일까....(눈물..)