백준 1799 비숍 C++

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

1799번: 비숍

제한 시간을 10초나 주길래 별 생각 없이 풀다가 낭패를 본 문제입니다. 

처음 생각했던 방안은 놓일 수 있는 모든 위치에 대해서 하나씩 놓아보면서

현재 최대값 결과인 result >= 현재까지 놓인 개수 res + 뒤에 남은 1인 칸

이면 탐색을 종료하도록 구성하였습니다.

 

하지만 이렇게 구성하니 시간초과가 떴고, 해당 방법을 이용하면 복잡도가 O(2^(N*N)) 임을 알게 되었습니다.

 

이를 해결하기 위해 다른 분들의 풀이를 참고하니 체스판의 흑백을 기준으로는 비숍이 이동하지 못하는 점을 이용하였습니다. 저도 이를 참고하여 해결하였습니다. ( O(2^(N/2 * N/2)) )

 

(하지만 dfs 시 첫 번째 1인 칸에 놓인 것을 다음 케이스로 이동시키지 않아서 몇 번의 틀렸습니다를 맛 봤다....)

 

remain 함수는 뒤 이어서 놓일 수 있는 칸을 구하는 함수, noFrom 함수는 (y,x)에 비숍을 놓음으로써 대각선들에 못 놓는 영역을 구하는 함수입니다.

 

(함수랑 변수 이름 짓기 너무 어렵다....)

 

그리고 모든 놓일 수 있는 시작 위치 (1) 을 기준으로 dfs를 진행합니다.

 

코드는 다음과 같습니다.

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

using namespace std;

int n;
int map[11][11];
bool check[11][11]; // 놓을 수 있는 지 여부
int result[2];

vector<pair<int,int>> vec0; // 까만 칸 가능한 위치들
vector<pair<int,int>> vec1; // 흰 칸 가능한 위치들

// 뒤에 남은 가능한 칸을 합친 것보다 현재 결과가 더 크면 탐색 안 해도 됨
// 까만칸 (0,0 색), 흰색 (0,1 색) 분리해서 계산 

void init()
{
  cin >> n;
  memset(check, false, sizeof(check));
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cin >> map[i][j];
      if(map[i][j] == 1) {
        check[i][j] = true; // 놓을 수 있음
        if((i + j) % 2 == 0)
          vec0.push_back({i, j});
        else
          vec1.push_back({i, j});
      }
    }
  }

  result[0] = 0; // 체스판 기준 까만칸
  result[1] = 0; // 체스판 기준 흰칸
}

vector<pair<int,int>> remain(int y, int x, int color)
{
  // 뒤에 남은 가능한 칸 개수
  // y, x : 현재 놓을 위치
  vector<pair<int, int>> v;
  
  for(int i = y; i < n; i++) {
    for(int j = 0; j < n; j++) {
      // 이전 칸
      if(i == y && j < x)
        continue;

      if(check[i][j] == true && (i + j) % 2 == color)
        v.push_back({i, j});
    }
  }

  return v;
}

vector<pair<int,int>> noFrom(int y, int x)
{
  // y, x 위치에 놓음으로써 만드는 불가능한 영역

  vector<pair<int, int>> v;

  v.push_back({y, x});
  check[y][x] = false;
  
  // 대각선 오른 위
  int ny = y - 1;
  int nx = x + 1;
  
  while(ny >= 0 && nx < n) {
    if(check[ny][nx] == true) {
      v.push_back({ny, nx});
      check[ny][nx] = false;
    }
    ny--;
    nx++;
  }

  // 대각선 오른 아래
  ny = y + 1;
  nx = x + 1;
  
  while(ny < n && nx < n) {
    if(check[ny][nx] == true) {
      v.push_back({ny, nx});
      check[ny][nx] = false;
    }

    ny++;
    nx++;
  }

  // 대각선 왼 위
  ny = y - 1;
  nx = x - 1;
  while(ny >= 0 && nx >= 0) {
    if(check[ny][nx] == true) {
      v.push_back({ny, nx});
      check[ny][nx] = false;
    }

    ny--;
    nx--;
  }

  // 대각선 왼 아래
  ny = y + 1;
  nx = x - 1;
  while(ny < n && nx >= 0) {
    if(check[ny][nx] == true) {
      v.push_back({ny, nx});
      check[ny][nx] = false;
    }

    ny++;
    nx--;
  }

  return v;
}

vector<pair<int,int>> dfs(int y, int x, int res, int color)
{
  // 탐색
  vector<pair<int,int>> v_no = noFrom(y, x);
  vector<pair<int,int>> v_rem = remain(y, x, color);

  // 뒤에 더 해도 안 됨
  if(result[color] >= res + v_rem.size() + 1)
    return v_no;

  // 마지막 놓을 수 있었던 경우
  if(v_rem.size() == 0) {
    result[color] = max(result[color], res + 1);
    return v_no;
  }

  // 다음 칸부터 놓을 수 있는 칸들에 놓아보기
  for(auto v : v_rem) {
    // 못 놓는 칸
    if(check[v.first][v.second] == false)
      continue;
    
    vector<pair<int,int>> v_no_ret = dfs(v.first, v.second, res + 1, color);

    // 못 놓게 만든 칸 되돌리기
    for(auto v2 : v_no_ret) {
      check[v2.first][v2.second] = true;
    }
  }

  return v_no;
}

int main()
{
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  init();
  vector<pair<int,int>> tmp;
  // 까만칸에 놓을 수 있는 경우
  if(!vec0.empty()) {
    for(auto v : vec0) {
      tmp = dfs(v.first, v.second, 0, 0);
      for(auto t : tmp) {
        check[t.first][t.second] = true;
      }
    }
  }
  // 흰 칸에 놓을 수 있는 경우
  if(!vec1.empty()) {
    for(auto v : vec1) {
      tmp = dfs(v.first, v.second, 0, 1);
      for(auto t : tmp) {
        check[t.first][t.second] = true;
      }
    }
  }
  cout << result[0] + result[1];
}