[C++] 9663. N-Queen

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

9663번: N-Queen

풀이

 

유의한 점

1. func1 : initiator

  -  malloc으로 배열을 동적할당 하려 했으나, 문제에서 최대의 N이 14라고 선언되어 있기 때문에 크기가 15인 배열 활용.

2. func2 : is_ok

  - 상하좌우, 대각선 검사를 통해 퀸이 들어갈 수 있는 곳인지 검사하는 함수

3. func3 : recursion

  - is_ok 함수의 리턴 값이 true면 퀸을 놓고, 행num을 증가시키고 열을 0으로 초기화 시켜 재귀함수를 호출하도록 함. 

#include <iostream>
#include <algorithm>
using namespace std;

int n, result_count;
int map[15][15] = { 0 };
int result[15];

void init_func()
{
    result_count = 0;
    cin >> n;
}

void print_map()
{

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int is_ok_2(int cur_row, int cur_col)
{
    if (result[cur_row] != 0) // 같은 행에 이미 말이 존재 
        return 0;

    for (int i = 0; i < cur_row; i++)
    {
        if (result[i] == cur_col + 1) // 같은 열에 이미 말이 존재
            return 0;
        else if ((result[i] - i) == (cur_col - cur_row + 1)) // 왼쪽 대각선에 말이 존재
            return 0;
        else if ((result[i] + i) == (cur_col + cur_row + 1)) // 오른쪽 대각선에 말이 존재
            return 0;
    }
    return 1;
}

void solution(int cur_row, int count)
{
    int is_up = false;
      
    if (count == n && cur_row == n)
        result_count++;

    for (int j = 0; j < n; j++)
    {
        if (is_ok_2(cur_row, j) == 1)
        {
            map[cur_row][j] = 1;
            result[cur_row] = j + 1;
            //print_map();
            solution(cur_row + 1, count + 1);
            map[cur_row][j] = 0;
            result[cur_row] = 0;
        }

    }
}

int main(void)
{
    init_func();
    solution(0, 0);
    cout << result_count;
}

---

처음 생각했던 알고리즘 및 문제점

1. time out 발생

  - try1 : 한행에 한개의 퀸이 없으면 바로 return하도록 함 -> 실패

  - try2 : 2차원 배열을 활용해서 이중 for문을 도는 것이 timeout의 원인이라고 판단

     -> 1차원 배열을 활용함.  ex) result[row] = c (row행의 말은 c열에 존재)

#include <iostream>
#include <algorithm>
using namespace std;

int n, result_count;
int map[15][15] = { 0 };

void init_func()
{
    result_count = 0;
    cin >> n;
}

//void print_map()
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            cout << map[i][j] << " ";
//        }
//        cout << "\n";
//    }
//    cout << "\n";
//}

void result_check()
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (map[i][j] == 1)
                count++;
        }
    }
    if (count == n)
        result_count++;
    //cout << "result count : "<< result_count<<"\n";
}

int is_ok(int cur_row, int cur_col)
{
    for (int i = 0; i < n; i++)
    {
        if (map[i][cur_col] == 1)
            return 0;
        for (int j = 0; j < n; j++)
        {
            if (map[cur_row][i] == 1)
                return 0;
            if ((abs(cur_row - i) == abs(cur_col - j)) && (map[i][j] == 1))
                return 0;
        }
    }
    return 1;
}

void solution(int cur_row)
{
    for (int i = cur_row; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (is_ok(i, j) == 1)
            {
                map[i][j] = 1;
                //print_map();
                solution(cur_row + 1);
                map[i][j] = 0;
            }
        }
    }
    result_check();
}

int main(void)
{
    init_func();
    //print_map();
    solution(0);
    cout << result_count;
}