글 읽기 - 백트래킹 대표문제 N-Queen 에서 시간초과 부분을 못 찾겠어요

beomyoung93 5년 전 0

단순히 답만 맞고 시간초과가 발생하는 부분을 못 짚겠습니다.

분명 불필요한 과정을 반복하는 부분이 있는거 같은데 그 부분을 못 찾겠습니다 ㅠㅠ

1) backtrack() 함수의 for()문

2) 서로 공격가능한 위치를 탐색하는 isPossible() 함수

이 두 부분에서 뭔가 잘못한거 같은데... 잘못된 부분을 캐치를 못 하겠습니다.

#include<stdio.h>
#define SIZE 16

int columns[SIZE];		//배치된 퀸의 위치, columns[2]=3 -> 2행 3열에 퀸 하나 배치!
int N;					//체스판 사이즈
int result = 0;

void backtrack(int depth);
bool isPossible(int row, int col);

int main() {
	//입력
	scanf("%d", &N);
	//처리
	backtrack(0);
	//출력
	printf("%d\n", result);
	return 0;
}
void backtrack(int depth) {
	if (depth == N) {
		result++;
		return;
	}
	for (int c = 0; c < N; c++) {
		if (isPossible(depth, c)) {			//둘 수 있다면(공격가능한 같은 행-열-대각선)
			columns[depth] = c;
			backtrack(depth + 1);
			//columns[depth] = NON;		// 덮어쓰는거라 원복 안함, isPossible()에서도 첫 번째 인수로 받은 행 이전만 검사해서 문제는 없음.
		}
	}
}
bool isPossible(int row, int col) {		//주어진 위치가 서로 공격하지 않는 위치인지 검사
	
	// 1. 행 검사 -> backtrack()호출 과정에서 행은 중복 불가능해서 검사 안함
	// 2. 열 검사
	for (int r = 0; r < row; r++) {		//인수로 주어진 row보다 이전 행들과 비교.
		if (columns[r] == col) {
			return false;
		}
	}
	// 3. 대각선 검사
	// 3-1. 기울기가 양인 대각선
	int slope;
	for (int r = 0; r < row; r++) {
		slope = r + columns[r];
		if (row + col == slope) {
			return false;
		}
	}
	// 3-2. 기울기가 음인 대각선
	for (int r = 0; r < row; r++) {
		slope = N + (r - columns[r]);
		if (N + (row - col) == slope) {
			return false;
		}
	}
	return true;
}

srand 5년 전 0

isPossible 함수에서 중복 검사를 조금 더 빠르게 바꾸시는건 어떨까요?

예를 들면 열 검사 의 for loop 대신,

char check_column[ 가로크기 ] = { 0 , } 과 같은 변수를 둬서

퀸을 둘 때 check_column[ 퀸 가로 위치 ] = 1 로 셋팅

검사는 check_column[ 가로 위치] == 1 ?

등등

가로, 세로, 우측 아래 대각선, 우측 위 대각선 검사를 빠르게 하면

수행 속도가 빨라질 것으로 예상 됩니다.

112224 5년 전 0

isPossible 함수에서 위치검사할때 수행횟수가 너무 많아서 그러실 거에요.

기울기 양,음에 관계없이 대각선이 한번에 검사가 가능한데, 별거 아닌 차이지만

문제의 시간복잡도 자체가 워낙 크다보니(대략 O(n^n)정도) 그 부분 하나로 TLE 받으신 것 같습니다!

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

문제

문제

출처

ICPC

백트래킹 대표문제 N-Queen 에서 시간초과 부분을 못 찾겠어요

beomyoung93 5년 전 0

srand 5년 전 0

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말