글 읽기 - 시간 초과가 나와야 정상인것 같은디 틀렸습니다가 나옵니다 도와주세용ㅠ

qkrtjdrb9573 7년 전 0

문제에서 주어진 케이스에 대해 13,14가 너무 늦습니다

시간을 획기적으로 줄일 수 있는 방법은 어떤 게 있고 적용하려면 제 코드에서 어떤 부분을 수정해야 할까요

코딩 잘하시는 분들, 이 불쌍한 영혼을 도와주세요!!

#include<cstdio>
#define COLS 20
using namespace std;
  
long long int N,cnt=0;
int dx[]={1,1,1,0,0,-1,-1,-1}, dy[]={1,0,-1,1,-1,1,0,-1};
 
//'a' is former rows, 'b' is former column positon 
void DFS(int a, bool visited[][COLS]) {
      
    if( a==N ) {
  
        cnt++;//counting number
        return;
    }
 
    bool tmp_arr[20][20];
 
    //preserve the value of 'visited' to tmp_arr
    for(int i=0; i<N; i++) 
        for(int j=0; j<N; j++)
            tmp_arr[i][j]=visited[i][j];
 
    for(int i=0; i<N; i++) {
              
        if( visited[a][i]==false ) {
              
            //checking position affected by the queen by changing 0 to 1
            for(int j=0; j<=N; j++) {
                for(int k=0; k<8; k++) {
                      
                    int nx=a+j*dx[k],ny=i+j*dy[k];
                    if( nx<0||ny<0||nx>=N||ny>=N ) continue;    
                      
                    visited[nx][ny]=true;
                                      
                }   
            }           
 
            DFS(a+1,visited); 
        }
 
     
    for(int i=0; i<N; i++) 
        for(int j=0; j<N; j++)
            visited[i][j]=tmp_arr[i][j];
         
    }
}
int main() {
     
    //'visited' array express the position that queen cannot stand.
    bool visited[20][20];
     
    scanf("%lld", &N);
    DFS(0,visited);
    printf("%lld\n",cnt);
      
    return 0;
}

zlzmsrhak 7년 전 0

여러가지 컷팅 알고리즘이 있습니다.

1. 퀸을 N개 놔야 한다는 조건 때문에, 모든 행과 모든 열에는 퀸이 하나씩 있어야 합니다.

이 때문에, 행을 기준으로 한 DFS도 성립합니다.

첫 번째 행에 하나를 놓아보고, 두 번재 행에 하나를 놓아보고, ... 하는 식으루요.

2. 퀸을 놓을 수 있는지 없는지를 확인할 때는, 각 행, 열 대각선에 퀸이 있는지를 체크하는 식으로 확인 가능합니다.

예를 들어, 세 번째 대각선에 퀸을 놓았다면, 세 번째 대각선에 퀸이 있다고 체크하는 식입니다.

이러면 다음에 퀸을 놓을 때 배열을 확인해서, 세 번째 대각선에 퀸이 없다는 것을 알 수 있겠죠.

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

문제

문제

출처

ICPC

시간 초과가 나와야 정상인것 같은디 틀렸습니다가 나옵니다 도와주세용ㅠ

qkrtjdrb9573 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말