nqueen 문제 해결을 위해 짜는 알고리즘 외에

안녕하세요 현재 nqueen 문제를 해결하기 위해 알고리즘들을 짜보고 있는 학생인데

현재 nqueen 문제를 해결하기 위해 대중적이고 보편적인 방법으로 쓰이는 알고리즘은 백트래킹으로 알고 있습니다.

하지만 다른 알고리즘으로 실행시 시간이 얼마나 차이가 날지 비교를 해보기 위해 BFS DFS를 구현해보고 있는데 재귀로 짜보고있는데 DFS를 이중배열에 적용 시켜보려니 너무 복잡하더군요

혹시 어떤 방향으로 알고리즘을 짜야하는지 대략적인 방향좀 잡아주셨으면 합니다 현재 코드는

bool solveDFS(int **board, int **visit, int row, int col, int number) {
	if (col >= number)
		return true;

	visit[row][col] = 1; //시작지점, 현재 위치 방문확인
	printf("%d ", board[row][col]);
	for (row; row < number; row++) {
		if (visit[row][col] = 1 && col < number)
			solveDFS(board, visit, row, col + 1, number);


	}
}

이런식으로 짜고 있구요 전부 다 짠건 아니예요

bool DFS(int row, int col, int number) {//시작할 부분인 행,열 그리고 배열크기를 받아온다.
	//게임 담당할 2차원 배열
	int** board;
	int** visit; //한번 거쳤는지 확인용

	board = (int**)malloc(sizeof(int*) * number);
	visit = (int**)malloc(sizeof(int*) * number);

	for (int i = 0; i < number; i++) {
		board[i] = (int*)malloc(sizeof(int) * number);
		visit[i] = (int*)malloc(sizeof(int) * number);
	}

	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			board[i][j] = 0;
			visit[i][j] = 0;
		}
	}
	//배열 초기화 완료

	//배열을 노드라 생각해보자

	if (solveDFS(board, visit, 0,0,number) == false) //백트래킹을 사용하는 부분
	{
		printf("Solution does not exist");
		return false;
	}

	printSolution(board, number);


	//사용한 동적할당 배열 메모리 반환
	for (int i = 0; i < number; i++) {
		free(board[i]);
	}
	free(board);

	return true;
}

이런식으로 DFS와 DFS로 nqueen을 해결하는 함수

두개를 짜보고 있습니다.

백트래킹 하실때 dfs로 안하셨었나요?

그거 반복문 안에서 재귀함수가 돌아서 로직을 도저히 이해를 못해 DFS를 그냥 O(n^n) 반복문으로 짜려고 했었는데 사람이 컴퓨터한테 할 짓이 아니란걸 깨닫고 다시 시도중입니다…

bool solveNQUtil(int **board, int col, int number)
{
	/* base case: If all queens are placed
	  then return true */
	/* 일반적 상태 : 만약 모든 퀸이 배치되어있다면 true를 리턴하라.*/
	if (col >= number)
		return true;

	/* Consider this column and try placing
	   this queen in all rows one by one */
	/* 모든 행(row)에 한번에 하나씩 이 열(column)이 기준일때 놓는걸 고려해본다
		즉 행만 계속 변함*/
	for (int i = 0; i < number; i++) //i = row
	{
		/* Check if the queen can be placed on
		  board[i][col] */
		/*퀸이 board[i][col]에 놓일수 있는지 체크하라*/
		/*i가 0부터 N-1 까지 계속 체크하면서 
			true 리턴 해주는 경우에만 작업시작*/
		if (isSafe(board, i, col, number))
		{
			/* Place this queen in board[i][col] */
			/*퀸을 board[i][col]에 위치하라*/
			board[i][col] = 1;

			/* recur to place rest of the queens */
			/*재귀함수 시작, 나머지 퀸을 놓기 위함*/
			/*위의 과정을 다시 반복*/
			if (solveNQUtil(board, col + 1, number))
				return true;

			/* If placing queen in board[i][col]
			   doesn't lead to a solution, then
			   remove queen from board[i][col] */
			/* 만약 퀸을 현재 board[i][col]에 놓을수 없다면 
				퀸을 board[i][col]에서 제거한다 */

			board[i][col] = 0; // BACKTRACK 
		}
	}

	/* If the queen cannot be placed in any row in
	   this colum col  then return false */
	/*만약 퀸을 이 열의 모든 행에 놓을 수 없다면 false리턴*/
	return false;
}

이게 백트래킹 부분인데 반복문 안에 있는 저 조건문,

isSafe 함수 위치만 잘 조절하면 단순 DFS가 될수 있을거 같은데 맞을까요?

이미 잘 구현하신거 같은데여 ㅎㅎㅎㅎ

저 백트래킹을 DFS로 다시 구현하려는데 nqueen 조건 부분을 어디에 둬야 할지가 제대로 안정해져서 돌려보는데 망하네여;