글 읽기 - 시간초과 질문입니다..

sujae03 6년 전 0

시간초과 때문에 질문드립니다.

제가 구현한 알고리즘은 다음과 같습니다.

1. Dir이라는 배열에 비숍이 갈 수 있는 길 ('1'인 경우) 저장해둡니다.

2. 갈 수 있는 길 (x,y) 좌표가 주어지면 대각선을 모두 체크하여 비숍이 놓일 수 있는지 체크합니다.

3. 만약 놓일 수 있다면 map에 '2'라고 비숍을 체크한 후 재귀를 통해 다음 갈 수 있는길을 똑같이 반복하며 놓일때마다 Cnt를 증가시킵니다.

만약 놓일 수 없다면, 다음 갈 수 있는 길에서 똑같이 2번부터 수행합니다.

하지만, 시간초과가 납니다 ㅠㅠ

시간초과를 줄일 수 있는 방법이 없을까요 ?

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int N;
int map[11][11];
int dir[2][101];            // 비숍이 갈 수 있는 좌표 저장
int size;                   // 갈 수 있는 최대 회수
int ResCnt;                 // 현재까지 비숍이 놓인 개수
int max;                    // 비숍이 놓인 최대 개수
void __Input()
{
    scanf("%d",&N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d",&map[i][j]);
            if (map[i][j] == 1) { dir[0][size] = i; dir[1][size++] = j; }
        }
    }
}
int __Chk(int x, int y)
{
    for (int i = 0; i < N; i++)
    {
        // 대각선 Check 후에 비숍이 놓일 수 없다면 0 return
        if ((x-i>=0 && y-i>=0) && map[x - i][y - i] == 2) { return 0; }
        if ((x+i<N && y+i<N)&& map[x + i][y + i] == 2) { return 0; }
        if ((x-i>=0 && y+i <N) && map[x - i][y + i] == 2) { return 0; }
        if ((x+i<N && y-i>=0) && map[x + i][y - i] == 2) { return 0; }
    }
    // 모두 검사하고 비숍이 놓일 수 있다면 1 return
    return 1;
}
void __DFS(int start)
{
    // 앞으로 count할 수 있는 비숍 개수 + 현재까지의 비숍 개수가 max보다 작거나 같다면 return
    if (size - start + ResCnt <=max) { return; }
    for (int i = start; i < size; i++)
    {
        int x = dir[0][i];
        int y = dir[1][i];
        if (!__Chk(x, y)) { continue; }
        map[x][y] = 2;
        ResCnt++;
        if (max < ResCnt) { max = ResCnt; }
        __DFS(i+1);
        map[x][y] = 1;
        ResCnt--;
    }
}
int main(void)
{
 
    __Input();
    __DFS(0);
    printf("%d\n",max);
    return 0;
}
 