[9663번] N-Queen 수정버전

[풀이를 위한 개념]

[9663번]N-Queen 포스팅을 참고하세요. (클릭시 해당 포스트가 새창으로 열립니다.)

[풀이과정]

#include<iostream>
 
 
using namespace std;
 
int n;
bool a[15][15];
int ans = 0;
 
 
 
bool check(int row, int col)    //퀸의 이동영역에 겹치는지 확인하는 함수
{
    for(int i =0;i<n;i++)        //직선방향 확인
    {
        if(i == row) continue;
        if(a[i][col])
        {
            return false;
        }
    }
 
    //대각선방향(체스를 행 윗방향으로 두고 있으므로 행 아래방향으로만 검사하면 된다)
    int x = row - 1;
    int y = col - 1;
    while(x>=0 && y>=0)
    {
        if(a[x][y] == true)
        {
            return false;
        }
        x -= 1;
        y -= 1;
    }
 
    //다른대각선방향
    x = row - 1;
    y = col + 1;
    while(x>=0 && y<n)
    {
        if(a[x][y] == true)
        {
            return false;
 
        }
        x -= 1;
        y += 1;
    }
 
    return true;
}
 
void calc(int row)
{
    if(row == n)                //끝까지 도착하면 가능한 경우이므로 정답
    {
        ans += 1;
    }
 
    for(int col = 0; col < n; col++)        //모든 열(column) 방문
    {
        a[row][col] = true;
        if(check(row, col))
        {
            calc(row+1);        //다음 행(row)로 이동
        }
        a[row][col] = false;    //백트래킹 (방문했던 흔적을 지우고 '가지치기' 한다)
    }
}
 
int main()
{
    cin >> n;
    calc(0);
    cout << ans << endl;
 
    return 0;
}
 

기존에 풀었던 답의 시간복잡도는 63줄에 의해서 O()가 됩니다. (check함수에서 n번 수행되는 작업이 row,col 한번씩 일어나므로 O(n*n))

이 check 함수를 변형해서 시간복잡도를 줄일 수 있습니다.

바로 모든 체스판에서 같은 직선에 위치한 체스를 표시하는 배열 + 대각선에 위치한 체스를 표시하는 배열을 만들면 됩니다.

[그림1] (별모양이 체스가 올라간 자리) 2가 표시된 구역은 퀸의 일직선 경로에 겹쳐 모두 들어갈 수 없으므로 배열 [0~3] 에서 2번 자리에 들어갈 수 없도록 불을 켜준다. 

[그림2] (별모양이 체스가 올라간 자리) 2가 표시된 구역은 퀸의 대각선 경로에 겹쳐 모두 들어갈 수 없으므로 배열 [0~6] 에서 2번 자리에 들어갈 수 없도록 불을 켜준다.

[그림2]는 같은 대각선 경로에 위치하는 점들을 모두 같은 숫자로 표현했다. 그리고 그 숫자들은 행+열(row+col)을 하면 나타낼 수 있다. 각 위치는 행과 열을 알면 행+열을 통해 어느 대각선에 해당되는지 판단할 수 있다.

[풀이과정]

#include<iostream>
 
 
using namespace std;
 
int n;
bool a[15][15];
 
bool check_col[15];                //최대 15x15이므로 행의 최대 개수는 15개
bool check_dig[40];
bool check_dig2[40];
 
bool check(int row, int col)
{
    // 수직방향
    if(check_col[col])
    {
        return false;
    }
 
    // 왼쪽 대각선
    if(check_dig[row+col])        //같은 대각선에 있는 숫자는 행+열
    {
        return false;
    }
    // 오른쪽 대각선
    if (check_dig2[row-col+n])    //다른 방향 대각선에 있는 숫자는 행-열+n
    {
        return false;
    }
 
    return true;
}
 
void calc(int row)
{
    if(row == n)
    {
        return 1;
    }
 
    int cnt = 0;
    for(int col = 0; col < n; col++)
    {
        if(check(row, col))
        {
            check_dig[row+col] = true;
            check_dig2[row-col+n] = true;
            check_col[col] = true;
            a[row][col] = true;
            cnt += calc(row+1);
            check_dig[row+col] = false;
            check_dig2[row-col+n] = false;
            check_col[col] = false;
            a[row][col] = false;
 
        }
    }
    return cnt;
}
 
int main()
{
    cin >> n;
    cout << calc(0) << endl;
 
    return 0;
}

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다