글 읽기 - 제 코드에서 속도를 더 줄일 수 있는 방법이 있을까요?

elshakzldk 4년 전 0

아래의 코드에서 시간 초과가 났는데 이제 막 알고리즘을 배우고 있는 상태라서 혼자서 해결하려 해봤지만 여기까지가 한계인 것 같습니다 ㅠㅠ 조금 더 고민 해보고 다른분들 코드를 검색해서 보려고 하는데 제 코드에서 더 개선해야 할 점이나 시간 초과가 난 부분에서의 피드백을 받아보고 싶습니다 감사합니다!

#define _CRT_SECURE_NO_WARNINGS	
#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define LEVEL 99999

int ar[LEVEL + 1];

bool N_Queen(int Cols, int N);
bool Test(int Cols, int N);

int main() {

	int N = 0;
	scanf("%d", &N);

	N_Queen(1, N);

	for (int i = 1; i <= N; i++) {

		printf("%d\n", ar[i]);
	}

	return 0;
}

bool N_Queen(int Cols, int N) {

	if (Cols == N + 1)return true;

	for (int i = 1; i <= N; i++) {

		ar[Cols] = i;
		if (Test(Cols, N))
			if (N_Queen(Cols + 1, N))
				return true;
	}
	return false;
}

bool Test(int Cols, int N) {

	for (int i = 1; i < Cols; i++) {

		if (ar[Cols] == ar[i] ||(abs(ar[Cols] - ar[i]) == abs(Cols - i)))
			return false;
	}
	return true;
}

jhlim 3년 전 0

해당 문제는 dfs로 풀수 없고(depth 설정 자체가 말이 안되죠) 특수한 로직에 따라 위치를 놓게 됩니다. 같은 유형의 dfs문제는 9663번: N-Queen에 존재합니다

jhlim 3년 전 0

https://en.wikipedia.org/wiki/Eight_queens_puzzle에서 해당 로직을 확인하실 수 있습니다.

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

문제

문제

출처

ICPC

제 코드에서 속도를 더 줄일 수 있는 방법이 있을까요?

elshakzldk 4년 전 0

jhlim 3년 전 0

jhlim 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말