알고리즘 공부중 2차원 배열의 동적생성 대한 질문

안녕하세요 제가 알고리즘, 인공지능을 공부하면서

Nqueen 문제를 해결하는 도중 2차원 배열 생성에서 문제가 생겼는데

의문점이 생겨 이렇게 질문을 드립니다

원래 코드는 지금은 주석 처리 되어있는

제가 그냥 정적으로 선언한 이중배열을 사용하면 코드가 잘 돌아가는데

N을 매크로 define으로 정의해 주는것이 아닌 N크기를 매번 바꿔보면서

동적으로 생성해주고 싶어 malloc을 사용했더니 문제가 발생하더라구요

다만 재밌는점은 전부 일단 0으로 초기화 하려고 하는거라

출력을 해보면 2차원 배열로 전부 0이 잘 찍히는데

sizeof를 쳐보면 4byte로 정수 딱 하나만 들어가있는 상황이 일어납니다

이러니 프로그램 결과문도 해답을 찾을수 없습니다. 이렇게 뜨구요

아직 free로 메모리 반환은 안했는데

왜 이러는지 의문이 가서 질문드립니다.

의심스러운 부분은

코드에서

int** board = malloc(sizeof(int*) * N);

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

이부분에서 비주얼 스튜디오가

NULL 포인터 board를 역참조하고 있습니다. 라고

오류는 아니지만 경고만 보내는데

이것 때문일까요?

/*int board[N][N] = { {0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
	};*/

	int** board = malloc(sizeof(int*) * N);

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			board[i][j] = 0;
		}
	}

	int count = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (count < i) {
				printf("\n");
				count++;
			}
			printf("%d ",board[i][j]);
			
		}
	}

	printf("\n%d\n", sizeof(board));


	if (solveNQUtil(board, 0) == false)
	{
		printf("Solution does not exist");
		return false;
	}

안녕하세요.

이므로

하게되면, 포인터 변수의 크기가 반환됩니다.
32비트 시스템에서는 4이고 64비트 시스템에서는 8이죠.

그 이유는 배열 변수와 포인터 변수는 다른 타입이기 때문에 그렇습니다.
(비슷하게 써서 헷깔려하시는 분들이 많지만)

전체 소스코드와 예제 입력을 올려주시면
정적으로한것을 동적으로 바꾸므로 문제가 생기는 부분을 제가 찾아보겠습니다.

1 Like
//0, -1은 정수형이면 memset 사용가능
memset(board, 0, sizeof board[0][0] * N * N);

for (int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++){
        printf("%d ", board[i][j]);
    }
    printf("\n"); //count 필요 없어요 마지막 LF 싫으면 j==0일때 \n하면 되겠죠?
}
1 Like
/* C/C++ program to solve N Queen Problem using
   backtracking */
#define N 4  //N을 정의
#include <stdio.h> 
#include <stdlib.h>
#include <stdbool.h> 
#include <time.h>

   /* A utility function to print solution */
void printSolution(int board[N][N])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			printf(" %d ", board[i][j]);
		printf("\n");
	}
}

/* A utility function to check if a queen can
   be placed on board[row][col]. Note that this
   function is called when "col" queens are
   already placed in columns from 0 to col -1.
   So we need to check only left side for
   attacking queens */
bool isSafe(int board[N][N], int row, int col)
{
	int i, j;

	/* Check this row on left side */
	for (i = 0; i < col; i++)
		if (board[row][i])
			return false;

	/* Check upper diagonal on left side */
	for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
		if (board[i][j])
			return false;

	/* Check lower diagonal on left side */
	for (i = row, j = col; j >= 0 && i < N; i++, j--)
		if (board[i][j])
			return false;

	return true;
}

/* A recursive utility function to solve N
   Queen problem */
bool solveNQUtil(int board[N][N], int col)
{
	/* base case: If all queens are placed
	  then return true */
	if (col >= N)
		return true;

	/* Consider this column and try placing
	   this queen in all rows one by one */
	for (int i = 0; i < N; i++)
	{
		/* Check if the queen can be placed on
		  board[i][col] */
		if (isSafe(board, i, col))
		{
			/* Place this queen in board[i][col] */
			board[i][col] = 1;

			/* recur to place rest of the queens */
			if (solveNQUtil(board, col + 1))
				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] = 0; // BACKTRACK 
		}
	}

	/* If the queen cannot be placed in any row in
	   this colum col  then return false */
	return false;
}

/* This function solves the N Queen problem using
   Backtracking. It mainly uses solveNQUtil() to
   solve the problem. It returns false if queens
   cannot be placed, otherwise, return true and
   prints placement of queens in the form of 1s.
   Please note that there may be more than one
   solutions, this function prints one  of the
   feasible solutions.*/
bool solveNQ()
{
	/*int board[N][N] = { {0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
		{0, 0, 0, 0,0,0,0,0},
	};*/

	int** board = malloc(sizeof(int*) * N);

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

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			board[i][j] = 0;
		}
	}

	int count = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (count < i) {
				printf("\n");
				count++;
			}
			printf("%d ",board[i][j]);
			
		}
	}

	printf("\n%d\n", sizeof(board));


	if (solveNQUtil(board, 0) == false)
	{
		printf("Solution does not exist");
		return false;
	}

	printSolution(board);



	return true;
}

// driver program to test above function 
int main()
{
	//실행 시간 비교를 위한 출력
	clock_t startFun, endFun; //시작, 끝 시간
	float res1; //시간 출력 결과물

	startFun = clock();
	
	solveNQ();
	
	endFun = clock();

	res1 = (float)(endFun - startFun) / CLOCKS_PER_SEC;

	printf("알고리즘 소요시간 : %f \n", res1);

	return 0;
}

전체 코드는 이런데 아마 함수에서 매개변수로 가져가는

컴퓨터가 int board[N][N] 이거도 다르게 볼 확률이 있을까요?

저는 int **board 이렇게 선언하고 채운거라…

원래 그냥 쉽게 N 넣어서 해도 되긴 하는데 뭔가

심심해보여서요

매개변수 타입을 고쳐보세요.

int board[N][N]에서 int** board로요.
그러면 잘 실행될 것 같습니다.

1 Like

여전히 실행해 봤는데 N을 4로 해도 답을 찾을수 없다가 뜨네요…

원래 4는 확정적으로 답이 하나가 나오는데 대체 왜이러는지 모르겠습니다

감사합니다 한개 함수뿐 아니라 다른 함수에 들어가는 board[n][n] 매개변수들을 전부 **board로 바꿨더니 잘 실행되었습니다!

2차원 배열과 더블 포인터는 다른 타입이라
타입 혼동하시면 안댑니당 ㅎㅎㅎ

포인터와 배열을 지금까지쉽게 이해하기 위해서 같은거라 생각하고 살아왔는데… 지금 아직도 이해가 되질 않네요

왜냐면 같지 않기 때문이죵 ㅎㅎㅎㅎ

한번 읽어보세요. 제가 쓴 글입니다.


빠진부분이 있는거 같아서 조금 내용을 추가했습니당 ㅎㅎㅎ

한줄로 이해할 수 있는 결론을 드리자면,

이겁니다. 네 같지 않습니다. ㅎㅎㅎㅎ