백준: Class 5 - 1799

</br> 클래스 5 계속
</br>

1799: 비숍

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

방법 1.

void func(int x, int y, int d){
    ans = max(ans, d);
    for(int i = x; i < n; i++){
        for(int j = y; j < n; j++){
            y = 0;
            if( mmap[i][j] == 1 && visited[i][j] == 0 ){
                visited[i][j] = 2;
                for(int k = 1; k < n; k++){
                    if( 0 <= i-k && 0 <= j-k && visited[i-k][j-k] <= 0 ) visited[i-k][j-k]--;
                    if( 0 <= i-k && j+k < n && visited[i-k][j-k] <= 0 ) visited[i-k][j+k]--;
                    if( i+k < n && 0 <= j-k && visited[i-k][j-k] <= 0 ) visited[i+k][j-k]--;
                    if( i+k < n && j+k < n && visited[i-k][j-k] <= 0 ) visited[i+k][j+k]--;
                }
                func(i, j, d+1);
                visited[i][j] = 0;
                for(int k = 1; k < n; k++){
                    if( 0 <= i-k && 0 <= j-k && visited[i-k][j-k] < 0 ) visited[i-k][j-k]++;
                    if( 0 <= i-k && j+k < n && visited[i-k][j+k] < 0 ) visited[i-k][j+k]++;
                    if( i+k < n && 0 <= j-k && visited[i+k][j-k] < 0 ) visited[i+k][j-k]++;
                    if( i+k < n && j+k < n && visited[i+k][j+k] < 0 ) visited[i+k][j+k]++;
                }
            }
        }
    }
}

이렇게 백트래킹으로 해서 풀린다면 여기 이 난이도에 있지 않겠지??
역시 시간 초과 난다
</br>

방법 2.

void func(int x, int y, int d){
    ans = max(ans, d);
    for(int i = x; i < n; i++){
        for(int j = y; j < n; j++){
            y = 0;
            if( mmap[i][j] == 0 ) continue;
            int ff = (j-i) + n-1;
            int ss = i+j;
            if( f[ff] == 0 && s[ss] == 0 ){
                f[ff] = 1;
                s[ss] = 1;
                func(i, j, d+1);
                f[ff] = 0;
                s[ss] = 0;
            }
        }
    }
}

비숍은 대각선만 신경 쓰면 된다
아 그럼 왼쪽에서 본 대각선과 오른쪽에서 본 대각선으로 나눠서 한 번 보면

0	40
1	30 41
2	20 31 42
3	10 21 32 43
4	00 11 22 33 44
5	01 12 23 34
6 02 13 24
7	03 14
8	04
즉 (j-i) + n-1

0	00
1	01 10
2	02 11 20
3	03 12 21 30
4	04 13 22 31 40
5	14 23 32 41
6	24 33 42
7	34 43
8	44
즉 i+j

이렇게 볼 수 있다
그럼 (i,j)에 비숍을 넣으면 f[(j-i) + n-1]와 s[i+j]에 체크하고 다음부턴 거기는 넘어가면 되는구나
확실히 빠른 것 같다

근데 시간 초과 난다!!
</br>

방법 3.

#include <bits/stdc++.h>

using namespace std;

vector< pair<int, int> > col[2];
int f[20], s[20];
int n, ans[2];

void func(int now, int d, int c){
    ans[c] = max(ans[c], d);
    for(int k = now+1; k < col[c].size(); k++){
        int i = col[c][k].first;
        int j = col[c][k].second;
        int ff = (j-i) + n-1;
        int ss = i+j;
        if( f[ff] == 0 && s[ss] == 0 ){
            f[ff] = 1;
            s[ss] = 1;
            func(k, d+1, c);
            f[ff] = 0;
            s[ss] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int a;
            cin >> a;
            if( a ){
                if( i%2 == j % 2 ) col[0].push_back(make_pair(i, j));
                else col[1].push_back(make_pair(i, j));
            }
        }
    }
    func(-1, 0, 0);
    func(-1, 0, 1);
    cout << ans[0] + ans[1] << endl;
}

최종 코드
바보 같이 func()에서 func(k, d+1, c);을 func(now, d+1, c);라 써서 계속 같은 거 돌아서 시간 초과 나더라
제대로 쓰니까 엄청 빨리 잘 돌아간다… 그래 어쩐지

그리고 흰색과 검은색을 나눠서 벡터에 넣었다. 포문으로 이중 배열인 체스판을 탐색할 필요 없이, 흰색 애들은 흰색끼리, 검은색 애들은 검은색끼리 비교하면 된다.
</br>

---

오늘은 8월 27일
스위프트랑 클라우드 수업이 끝났다
같이 수업 들은 분들이랑 스터디를 하게 돼서 학기 중에 복습 겸 포스트를 올려야 겠다
물론 알고리즘 문제도 매일 한 문제라도 풀어야지
</br>