[TWONQR] 백트랙킹을 써서 재귀 탐색으로 2n Rook and Queen을 풀려고 했는데

  • ntinamu
    ntinamu

    TWONQR

    #include <iostream>
    #include <string.h>
    #include <stdlib.h>
    using namespace std;
    
    typedef struct _node
    {
        int row;
        int col;
    
        int type;
    }Node;
    
    Node board[20];
    int size;
    int cnt;
    
    void init(void)
    {
        memset(board, 0, sizeof(Node) * 20);
    
        cnt = 0;
    }
    
    int isAvailable(int row, int col, int type)
    {
        for (int i = 0; i < row; i++)
        {
            if (board[i].type == 1)
            {
                if (board[i].col == col)
                    return 0;
    
                else if (abs(col - board[i].col) == abs(row - board[i].row))
                    return 0;
            }
            else if (board[i].type == 2)
            {
                if (board[i].col == col)
                    return 0;
    
                if (type == 1)
                {
                    if (abs(board[i].col - col) == abs(board[i].row - row))
                    {
                        return 0;
                    }
                }
            }
        }
    
        return 1;
    }
    
    void backTracking(int queenNum, int rookNum, int level)
    {
        if (level == 2 * size)
        {
            cnt = (cnt + 1) % 20130203;
            return;
        }
    
        for (int i = 0; i < 2 * size; i++)
        {
            if (rookNum != 0)
            {
                if (isAvailable(level, i, 2))
                {
                    board[level].row = level;
                    board[level].col = i;
                    board[level].type = 2;
                    backTracking(queenNum, rookNum - 1, level + 1);
                }
                else
                    continue;
            }
    
            if (queenNum != 0)
            {
                if (isAvailable(level, i, 1))
                {
                    board[level].row = level;
                    board[level].col = i;
                    board[level].type = 1;
                    backTracking(queenNum - 1, rookNum, level + 1);
                }
            }
        }
    }
    
    int main(void)
    {
        int testcase;
        int itx;
    
        cin >> testcase;
    
        for (itx = 0; itx < testcase; itx++)
        {
            init();
    
            cin >> size;
    
            backTracking(size, size, 0);
    
            cout << cnt << endl;
        }
    
        return 0;
    }
    

    백트랙킹을 이용해서 탐색으로 경우의 수를 셀려고 하는데 계속 시간 초과가 뜨네요

    계속 생각을 해봐도 효율적인 알고리즘이 떠오르질 않습니다 ㅠㅠ

    N-Queen 문제는 백트랙킹을 이용해서 풀리던데 이 경우는 왜 시간초과가 뜨는걸까요?

    그리고 어떤 식으로 접근해야 하는지 도저히 모르겠는데 조금이라도 도움을 주신다면 감사하겠습니다


    9년 전
1개의 댓글이 있습니다.
  • WeissBlume
    WeissBlume

    N제한이 작기 때문에 각각의 N에 대해 자신의 컴퓨터에서 답을 미리 계산한 다음 이를 출력만 하는 코드를 작성해서 제출하면 됩니다.
    효율적으로 작성하려면 좀 더 생각해보신 다음 풀이를 읽어보세요.


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.