백준 g1 1799 비숍 c++

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

1799번: 비숍

 

시간초과 났던 이유

 

처음에는 해당 칸에 비숍을 놓냐 안 놓냐로 O(2^100)의 시간이 걸릴 거란 걸 알았지만, 딱히 다른 해결책이 떠오르지도 않고

1. 해당 칸에 놓을 수 있을지 없을지 <- 반으로 줆

2. 남은 칸에 모조리 비숍을 놓아도 현재 mx보다 안 되면 return

 

이 두 가지 return 조건으로 되나? 안 될 것 같지만 일단 해보자 라고 해서 코드를 짜봤다

if 남은 칸 개수 + 현재 값 <= 현재mx
	return
if 해당 칸에 놓을 수 있으면
	놓기
    func(k+1)
    놓았던 거 되돌리기

// 안 놓을 때
func(k+1)

그러나 역시나 시간초과가 떴고, 결국 백준 질문 게시판을 참고했다.

 

풀이

체스판의 검은 칸과 흰 칸을 나누어서 생각한다. 어차피 비숍은 같은 대각선끼리만 겹치지 않으면 되기 때문에,

검은 칸에 놓을 수 있는 max값 + 흰 칸에 놓을 수 있는 max값 을 더해주면 그게 최대로 놓을 수 있는 비숍의 개수이다.

O(2^100) -> O(2^50)+O(2^50)으로 줄일 수 있다.

 

현재 대각선을 쓸 수 있는지 없는지는 used1과 used2 배열을 이용한다.

used1은 우상향 대각선, used2는 좌상향 대각선을 나타낸다.

x+y가 같은 값들이 같은 우상향 대각선에 있고, x-y가 같은 값들이 같은 좌상향 대각선에 있다. 

 

대각선의 개수는 N+1이 될 때마다 2개씩 늘어나므로, 총 2N-1개다.

 

수도 코드

// mx는 최대값, ans는 dfs로 지금까지 계산해온 값

func(int k) // vec[k]를 놓을 차례
	if k == vec.size()
    	mx = max(mx, ans)
        return
    if 남은 칸 개수 + ans <= mx
    	return
        
    if 현재 칸 놓을 수 있으면
    	used1, used2 체크
        ans++
        
      	func(k+1)
        
        used1, used2 체크 풀기, ans--
    
    //현재 칸에 놓지 않는 경우의 수
    func(k+1)

 

 

코드

/*boj g1 1799 비숍*/
#include <iostream>
#include <tuple>
#include <vector>
#define MAXN 12
using namespace std;

int N;
int board[MAXN][MAXN];
vector<pair<int, int>> locB; // x+y가 짝수
vector<pair<int, int>> locW; // x+y가 홀수
int used1[2 * MAXN];         // 어차피 B, W 겹칠 일은 없으니 그냥 쓰자
int used2[2 * MAXN];

int mxB = 0;
int mxW = 0;
int ans = 0;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];

            if (board[i][j] == 1) {
                if ((i + j) % 2 == 0)
                    locB.push_back({i, j});
                else
                    locW.push_back({i, j});
            }
        }
    }
}

void funcB(int k) { // locB[k]를 놓아야 함
    if (k == locB.size()) {
        mxB = max(mxB, ans);
        return;
    }

    if (locB.size() - k + ans <= mxB) { // 남은 칸을 모조리 채워도 현재 mx보다 작을 때
        return;
    }

    int x, y;
    tie(x, y) = locB[k];

    if (!used1[x + y] && !used2[x - y + N - 1]) { // 현재 칸에 놓을 수 있을 때
        used1[x + y] = 1;
        used2[x - y + N - 1] = 1;
        ans++;

        funcB(k + 1);

        used1[x + y] = 0;
        used2[x - y + N - 1] = 0;
        ans--;
    }

    funcB(k + 1); // 현재 칸에 놓지 않고 다음 칸 진행
}

void funcW(int k) { // locW[k]를 놓아야 함
    if (k == locW.size()) {
        mxW = max(mxW, ans);
        return;
    }

    if (locW.size() - k + ans <= mxW) { // 남은 칸을 모조리 채워도 현재 mx보다 작을 때
        return;
    }

    int x, y;
    tie(x, y) = locW[k];

    if (!used1[x + y] && !used2[x - y + N - 1]) { // 현재 칸에 놓을 수 있을 때
        used1[x + y] = 1;
        used2[x - y + N - 1] = 1;
        ans++;

        funcW(k + 1);

        used1[x + y] = 0;
        used2[x - y + N - 1] = 0;
        ans--;
    }

    funcW(k + 1); // 현재 칸에 놓지 않고 다음 칸 진행
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();

    ans = 0;
    funcB(0);

    ans = 0;
    funcW(0);
    cout << mxB + mxW << "\n";
}