글 읽기 - [C] N-Queen 문제에서 시간을 단축하는 방법을 알고 싶습니다.

alsrl9 3년 전 0

N-Queen 문제에서 정답 처리됐지만 시간을 단축시키는 방법을 알고 싶어서 질문을 올립니다.

하나의 Row에 하나의 Queen만 들어갈 수 있다는 점을 이용해서

Queen을 자리에 놓으면 해당 Column의 Queen 이하로 모든 점과 왼쪽 아래 대각선, 오른쪽 아래 대각선을 탐색하며 Queen을 놓을 수 없게 처리했습니다.

모든 경우를 탐색하기 위해서 재귀적으로 처리하고 탐색 후에는 Queen을 놓기 전 상태로 되돌리는 방식을 선택했습니다.

여러 시도 끝에 불필요한 탐색을 줄여서 정답으로 처리되었지만 실행 시간이 2000ms를 넘습니다.

다른 분들은 1000ms 정도에 문제를 해결한 분도 더러 계신데 코드를 직접 봐도 이해하지 못하겠습니다.

어떤 점 때문에 이렇게 시간차이가 나는 걸까요?

알려주시면 감사하겠습니다.

#include <stdio.h>
#include <string.h>

int N; // 1~14
int check[15][15];
int dRow[2] = { 1, 1 };
int dCol[2] = { 1, -1 };
int cntCase;

void put_queen(int board[][15], int row, int col){
	int newRow, newCol;

	board[row][col] = 1;
	for (int i = col + 1; i < N; i++)
		board[row][i] = 1;
	for (int i = row + 1; i < N; i++)
		board[i][col] = 1;


	for (int i = 0; i < 2; i++){
		newRow = row;
		newCol = col;

		while (1){
			newRow += dRow[i];
			newCol += dCol[i];
			if (newRow < 0 || newRow >= N || newCol < 0 || newCol >= N) break;
			board[newRow][newCol] = 1;
		}
	}
}

void search(int board[][15], int row, int col, int cntQueen){
	int checkTemp[15][15];

	if (cntQueen == N){
		cntCase++;
		return;
	}

	memcpy(checkTemp, board, sizeof(checkTemp));

	for (int j = 0; j < N; j++){
		if (board[row + 1][j] == 0){
			put_queen(checkTemp, row + 1, j);
			search(checkTemp, row + 1, j, cntQueen + 1);
			memcpy(checkTemp, board, sizeof(checkTemp));
		}
	}
}

int main(){
	scanf("%d", &N);
	search(check, -1, 0, 0);
	printf("%d", cntCase);
	return 0;    
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C] N-Queen 문제에서 시간을 단축하는 방법을 알고 싶습니다.

alsrl9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말