글 읽기 - C++ 시간초과 문의

pmj6541 2년 전 0

할 수 있는 최적화는 다 해봤다고 생각하는데 아직 해결이 안되네요ㅠ

손 볼 부분 알려주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt = 0;
int depth = 0;
int N;
int firstTimes = 0;
int secondTimes = 0;
void dfs(int, int, vector<pair<int, int>>, vector<bool>, vector<bool>);
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>N;
  vector<pair<int, int>> Queens;
  vector<bool> isThereQueenX(16);
  vector<bool> isThereQueenY(16);
  for(int i=0;i<N;i++){
    isThereQueenX[i] = false;
    isThereQueenY[i] = false;
  }
   
  for(int i=0;i<N;i++)
    dfs(i,0,Queens,isThereQueenX, isThereQueenY);
  cout<<cnt;
}

void dfs(int x, int y, vector<pair<int, int>> Queens, vector<bool> isThereQueenX, vector<bool> isThereQueenY){
  for(int j=0;j<Queens.size();j++){
    if(Queens[j].first-x == Queens[j].second-y||x-Queens[j].first == Queens[j].second-y){
      return;
    }
  }
  if(y == N-1){
    cnt++;
    isThereQueenY[y] = true;
    return;
  }
  Queens.push_back(make_pair(x,y));
  isThereQueenX[x] = true;
  if(Queens.size() != N){
    for(int i=0;i<N;i++){
      if(!isThereQueenX[i]&&!isThereQueenY[y])
        dfs(i,y+1,Queens, isThereQueenX, isThereQueenY);
    }
  }
  return;
}

euphoric_n 2년 전 1

void dfs(int, int, vector<pair<int, int>>, vector<bool>, vector<bool>);

구현하신 dfs 함수의 선언부입니다.

인자로 vector<pair<int, int>>, vector<bool>, vector<bool>을 넘겨주도록 되어있는데요

매번 dfs함수가 호출될 때마다 vector들을 복사하고 전달하면서 함수를 실행하기 때문에 시간 초과가 발생하게 됩니다.

불필요한 복사를 피하기 위해서는 vector<pair<int, int>> &Queens 와 같이 참조자를 사용하거나, 필요한 vector들을 전역변수로 설정하는 방법 등이 있겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++ 시간초과 문의

pmj6541 2년 전 0

euphoric_n 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말