[백준 1799] 비숍

 

 

 백트래킹 문제다. 그래프 이론이나 탐색 유형의 문제는 곧 잘 푸는 편인데, 이건 핵심 아이디어가 바로 떠오르지 않아서 꽤 많은 시간을 소요했다. 브루트 포스를 활용하면 O(2^(n^2))에 해당하므로, 풀 수가 없다.

 

 그래서 처음 시도한 방법은 그리디 알고리즘이었다. 비숍을 놓을 수 있는 빈칸 배열을 저장해 두고, 각각 대각선을 탐색해서, 해당 칸에 비숍을 놨을 때 놓을 수 없게 되는 칸의 수를 셌다. 그리고 이를 우선순위 큐에 집어넣고, 손실이 가장 적은 칸부터 하나씩 채워보는 방법을 썼다. 몇 가지 직접 떠올린 케이스들에 대해서는 꽤나 잘 먹혔지만, 이 방법은 시간복잡도만 우선했을 뿐, 최적해 찾는 것을 보장할 수 있느냐를 스스로 증명하지 못했다. 결과는 아니나 다를까 중간에 틀렸습니다를 받았다.

 

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> point;
typedef pair<point, vector<point> > blank_info;

int n;
bool chessBoard[10][10];
int dx[4] = {1, 1, -1, -1};
int dy[4] = {-1, 1, 1, -1};

void checkImpact(blank_info& bi) {

    for(int dir=0; dir<4; dir++) {
        int y = bi.first.first;
        int x = bi.first.second;
        while(y+dy[dir]>=0 && y+dy[dir]<n && x+dx[dir]>=0 && x+dx[dir]<n) {
            y += dy[dir];
            x += dx[dir];

            if(chessBoard[y][x]) {
                bi.second.push_back({y, x});
            }
        }
    }
}

struct compare {
    bool operator() (blank_info a, blank_info b) {
        if(a.second.size() != b.second.size()) {
            return a.second.size()>b.second.size();
        } else {
            return a.first > b.first;
        }
    }
};


int main() {
    cin >> n;
    vector<blank_info> blankInfoList;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> chessBoard[i][j];
            if(chessBoard[i][j]) blankInfoList.push_back({{i, j}, vector<point>()});        
        }
    }

    priority_queue<blank_info, vector<blank_info>, compare> pq;

    for(auto bi: blankInfoList) {
        checkImpact(bi);
        pq.push(bi);
    }

    int result = 0;

    while(!pq.empty()) {
        auto bi = pq.top();
        pq.pop();

        if(chessBoard[bi.first.first][bi.first.second]) {
            result++;
            for(auto p: bi.second) {
                chessBoard[p.first][p.second] = false;
            }
        }
    }

    cout << result;

}

 

 

 그다음엔 조금 조잡한 브랜치 앤 바운드를 사용해 보았다. 각 빈칸마다 비숍을 뒀을 때, 영향을 받게 되는 칸들을 리스트에 저장했다. 그리고 DFS를 통해서 모든 빈칸을 탐색하면서, promising이라는 가중치를 따로 계산했다. 해당 칸에 비숍을 놓은 경우 뒤에 유효한 빈칸이 몇 개 남는지를 반영해서 promising 값을 경신하고, 그 값을 현재까지 놓은 비숍의 수에 더해 현재 최대로 비숍을 놓은 수와 비교했다. 하지만 결국에는 비숍을 놓는 경우와 놓지 않는 경우를 구분해 DFS를 반복해줘야 했고, 이는 최악의 경우 브루트포스와 크게 차이 나지 않을 것 같았다. 

 예상대로 시간 초과되는 케이스들이 보였고, 아마 n이 10이고 모든 칸이 빈칸일 때가 Worst Case였을 것으로 예상한다.

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> point;
typedef pair<point, vector<point> > blank_info;

int n, maxNum=0, promising;
bool chessBoard[10][10];
int dx[4] = {1, 1, -1, -1};
int dy[4] = {-1, 1, 1, -1};
vector<blank_info> blankInfoList;

void dfs(int curNum, int depth) {
    if(curNum+promising<=maxNum) {
        return;
    }
    maxNum = max(maxNum, curNum);
    if(depth==blankInfoList.size() || promising==0) {
        return;
    }

    auto& bi = blankInfoList[depth];
    int dropNum = 0;
    if(chessBoard[bi.first.first][bi.first.second]) {
        vector<point> changed;
        dropNum++;
        chessBoard[bi.first.first][bi.first.second] = false;

        for(auto p: bi.second) {
            if(chessBoard[p.first][p.second]) {
                changed.push_back({p.first, p.second});
                chessBoard[p.first][p.second] = false;
                if(bi.first.first<p.first || (bi.first.first==p.first && bi.first.second<p.second)) {
                    dropNum++;
                }
            }
        }

        promising-=dropNum;
        dfs(curNum+1, depth+1);
        promising+=dropNum;

        chessBoard[bi.first.first][bi.first.second] = true;
        for(auto p: changed) {
            chessBoard[p.first][p.second] = true;
            dropNum--;
        }
    }

    promising -= dropNum;
    dfs(curNum, depth+1);
    promising += dropNum;
}

void checkImpact() {
    for(auto& bi: blankInfoList) {
        for(int dir=0; dir<4; dir++) {
            int y = bi.first.first;
            int x = bi.first.second;
            while(y+dy[dir]>=0 && y+dy[dir]<n && x+dx[dir]>=0 && x+dx[dir]<n) {
                y += dy[dir];
                x += dx[dir];

                if(chessBoard[y][x]) {
                    bi.second.push_back({y, x});
                }
            }
        }
    }
}


int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> chessBoard[i][j];
            if(chessBoard[i][j]) blankInfoList.push_back({{i, j}, vector<point>()});        
        }
    }
    promising = blankInfoList.size();
    checkImpact();
    dfs(0, 0);

    cout << maxNum;

}

 

 

 이쯤에서 어떻게든 칸 단위로 탐색하는 것을 되도록 피해야겠다고 생각했다. 그러다가 생각한 것이 대각선을 상좌 - 하우 / 상우 - 좌하 방향 두 종류로 나눠서 배열을 만들고, 비숍을 놓을 수 있는지 여부를 더 빠르게 판별하는 방법이었다. 

 이를 통해 메모리 소모나 불필요한 레퍼런싱 연산을 많이 줄였지만, 정작 본 로직의 퍼포먼스는 그다지 개선되지 않은 형태였기 때문에, 역시나 Worst Case를 넣으니 답을 제때 출력하지 못했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> point;

int n, maxNum=0;
bool chessBoard[10][10];

bool leftDiagonal[19] = {false, };
bool rightDiagonal[19] = {false, };

vector<point> blankList;

void dfs(int cnt, int depth) {
    if(cnt+blankList.size()-depth <= maxNum) {
        return;
    }

    if(depth == blankList.size()) {
        maxNum = max(maxNum, cnt);
        return;
    }

    int y = blankList[depth].first;
    int x = blankList[depth].second;

    if(!leftDiagonal[y+x]
     && !rightDiagonal[x-y+n]) {
        leftDiagonal[y+x] = true;
        rightDiagonal[x-y+n] = true;

        dfs(cnt+1, depth+1);

        leftDiagonal[y+x] = false;
        rightDiagonal[x-y+n] = false;
    }

    dfs(cnt, depth+1);
}

int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> chessBoard[i][j];
            if(chessBoard[i][j]) blankList.push_back({i, j});        
        }
    }

    dfs(0, 0);

    cout << maxNum;

}

 

 

 이후에, 대각선 단위 계산에 대해 좀 더 생각하다가, 문득 N-Queen 문제를 응용하면 되지 않을까 하는 생각이 들었다. 비숍의 움직임이 대각선이라서 쉽사리 생각이 닿지 않았었는데, 생각해 보면 체스판을 45도 기울이면 가로와 세로로만 움직이는 N-Queen 꼴이 될 거 같다는 아이디어였다.

 절댓값 연산을 이용해 대각선 단위로 체스판을 탐색하는 형태로 작성하면 메모리를 조금 더 아낄 수 있을 것 같았으나, 그러면 탐색 과정에서 부가적인 연산이 조금 늘고 메모리 제한은 넉넉했기 때문에, 그냥 45도 기울인 체스보드로 아예 치환해 버리는 방법을 택했다.

 N-Queen 같은 형태로 만든 덕에 최대 depth까지 DFS를 진행하는 과정은 빨라졌으나, Worst Case는 여전히 빠듯했다. N-Queen 문제와는 다르게, 조건에 맞는 해의 존재 여부를 판별하는 것이 아니라 최적해를 찾는 문제이기 때문에 필연적으로 모든 케이스를 확인해야 했기 때문이다.

 그래서 위에서 promising 값을 이용했던 것처럼 탐색 깊이와 전체 보드의 길이를 이용해 bound를 계산해 pruning 해주었고, 그제서야 정답 판정을 받아낼 수 있었다. 

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> point;

int n, maxNum=0;
int bishop[19];
bool chessBoard[19][19] = {false};

void dfs(int cnt, int depth) {
    if(cnt+(n*2-1)-depth <= maxNum) return;

    if(depth == n*2-1) {
        maxNum = max(maxNum, cnt);
        return;
    }
    
    for(int i=0; i<n*2-1; i++) {
        if(chessBoard[depth][i]) {
            bool flag = true;
            for(int j=0; j<depth; j++) {
                if(bishop[j]==i) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                bishop[depth] = i;
                dfs(cnt+1, depth+1);
            }
        }
    }

    bishop[depth] = -1;
    dfs(cnt, depth+1);
}

int main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin >> chessBoard[i+j][j-i+n-1];    
        }
    }

    dfs(0, 0);
    cout << maxNum;
}