백준 9663 N-Queen (C++)

문제설명

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

9663번: N-Queen

 

문제 해결 

백트래킹(DFS)을 이용해서 푸는 문제이다. 한 step당 하나의 퀸을 일단 두고, 조건에 만족하면 다음 step으로 넘어가는 방식이다. 

주의할 점은 두 가지이다.

1. visit 배열을 두어 현재 둔 위치를 체크해두되, DFS 재귀문 호출 뒤에 다시 풀어준다. 

2. 대각선 인덱스 헷갈리지 않게 조심한다. 대각선 기준으로 찾을 때, 현재 step 이전에 y가 더 큰 경우도 고려해주어야 한다. 

 

트러블 슈팅 + 개선안 

나는 확인하는 체스판 배열 (v배열)을 2차원으로 두어도 시간 초과가 나지 않았는데, 그 이유는 현재 퀸 위치가 x, y라면, 현재 위치 기준으로 (x - 1, y - 1), (x - 2, y - 2) .. 이러한 식으로 for문을 한번만 사용하여 풀었기 때문이다. 그래서 더더욱.. 풀면서 2차원으로 v배열을 둘 필요가 없다는 사실을 깨달았다. 인덱스 계산하다가 조금 꼬여서 그 부분에서 시간을 조금 사용하였다.

 

1차원 배열 버전으로도 풀어보고 싶어서 두 번 풀었다. v 배열을 1차원으로 두고 각 배열에 현재 queen의 위치를 적어둔다면, 훨씬 간편하게 이 문제를 해결할 수 있다. 대각선 인덱스 구하는 노가다를 안해도 된다.. 그리고 두 버전으로 풀어보니 시간도 2배정도 준 모습을 확인할 수 있었다. 

기존 풀이

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

using namespace std;
int v[16][16] = {0, };
int n;
int sum = 0;

int check(int x, int y) 
{
    for (int i = 1; i <= max(x, y); i++)
    {
        if ((x - i) >= 0 && (y - i) >= 0)
            if (v[x- i][y - i] == 1)
                return (0);
        if ((x - i) >= 0 && (y + i) < n)
            if (v[x - i][y + i] == 1)
                return (0);
    }
    for (int i = 0; i < x; i++)
        if (v[i][y] == 1) //세로줄 검사 
            return (0);      
    return (1);
}

void dfs(int step)
{
    if (step == n)
    {
        sum++;
        return ;
    }
    for (int i = 0; i < n; i ++)
    {
        v[step][i] = 1;
        if (check(step, i))
            dfs(step + 1);
        v[step][i] = 1;
    }
}
int main(void)
{
    cin >> n;
    dfs(0);
    cout << sum << "\n";
    return (0);
}

 

v배열을 1차원으로 줄여 개선한 풀이 

 

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

using namespace std;
int v[16] = {0, };
int n;
int sum = 0;

int check(int step) 
{
    for (int i = 0; i < step; i++)
    {
        if (abs(v[step] - v[i]) == step - i)
            return (0);
        if (v[step] == v[i])
            return (0);
    }
    return (1);
}

void dfs(int step)
{
    if (step == n)
    {
        sum++;
        return ;
    }
    for (int i = 0; i < n; i ++)
    {
        v[step] = i;
        if (check(step))
            dfs(step + 1);
    }
}
int main(void)
{
    cin >> n;
    dfs(0);
    cout << sum << "\n";
    return (0);
}

 

결과