깊이 우선 알고리즘 구현에 있어

저도 지난 학기 Algorithm 수업 때 해서 정겹네요.

저희 교수님은 5*5 puzzle 를 내서 얘들 완전히 죽였다는.....(-_-).

원래 Sam Loyd 가 처음 이 문제를 냈을 때는 15(4*4) 였었다고 하는데...

아시겠지만

조건검사

처리
재귀호출
역처리.

입니다.

잘은 모르겠습니다만 역처리가 빠진 느낌입니다.

저는 되추적 Algorithm 구현시 전역변수를 즐겨 만듭니다.

이것이 data hiding 관점에서 좋은 것이 아니라는 것은 압니다만 편하다는 생각에 막 씁니다.(-_-)

block 안에 생성되는 자동변수는 block 이 종료되면서 사라지는데 이를 이용해서 보통 되추적 Algorithm 을 pseudo code 로 설명할 때는 역처리가 빠지기 마련입니다.

즉 재귀호출이 이루어지면서 매개변수에 필요한 정보를 몽땅 넣어 복사하는 거죠.
이렇게 되면 해당깊이에서 빠져나오면 원래대로 돌아가게 됩니다.

하지만 전역변수를 건드리면 수작업으로 원래상태로 돌려놔야 합니다.

이 방법을 제가 즐겨쓰는 이유는 우선 memory 가 아껴지기 때문이죠.
몽땅 매개변수에 넣어 복사하면 재귀의 깊이에 따라 memory 요구량이 늘어나니까...
또한 복사를 몽땅하는 것에 비해 처리량이 즐어들지 않을까라는 막연한 기대심리도 있습니다...(-_-)... 이부분은 제가 잘못생각하는거죠. (경우에 따라 다릅니다. 특히 최신의 Itanium 은 공유변수를 사용하는 것보다 자동변수가 최적화를 통해 더 좋은 성능을 내는 경우가 많다고 하더군요.)

즉 저는 puzzle table 하나가지고 바꿨다가 돌려놓으면서 작업을 합니다.
이 경우 추가적으로 생성했다가 없애는 작업은 direction 만 하면 되죠.

gnoygnas 씨가 작성하신 것은 비록 동적할당을 사용한 수작업입니다만 부모 node 의 value 는 보존되고, 자식 node 에 value 를 복사하므로 문제될 것은 없다고 생각합니다.

다만 이렇게 할 경우 동적할당된 자식 node 들은 재귀호출을 빠져나오기 전에 해제해주셔야 memory 가 반환되겠죠.

source 어디에서도 malloc 은 있으나 free 는 없네요.

최대재귀깊이가 3일때는 그나마 괜찮지만 아마도 8 puzzle 이 3 에서 끝날 거라고 생각되지 않는군요.

아마도 더 늘리실텐데 그 때에는 memory 가 감당 못할 수도 있습니다.

또한 iPuzzle과 gPuzzle 은 동적할당할 이유가 없어보입니다.

마찬가지로 가급적 각 node 의 생성은 자동변수로 생성하는 것이 좋겠습니다.
(그렇게 하면 free 도 필요없죠.)

물론 각 node 를 재귀를 통해 decision tree 를 남겨두는 것이 목적이 아니라면 말입니다만...

동적할당과 해제는 상당히 재미있는 기법입니다만 작은 program 이나 환경에 따른 문제가 아니라면 필요한 경우는 자료구조를 만드는 것 이외에는 없습니다.

동적할당과 해제는 OS 에 의해서 처리되는데 그것이 kernel mode 로 넘어가서 처리되든 그렇지 않든 system call 을 사용하고, OS 의 memory 관리작업에 의해 성능저하를 불러올 수 있습니다.

또한 memory 의 동적관리로 인해 OS 는 추가적인 memory 를 소모해야 합니다.

다른 이야기로 넘어가서 이전에 제가 적었던 coordinate 는 이차원 배열로 table 을 표현할 때 적당한 방법입니다.

gnoygnas 씨는 일차원배열을 사용했더군요.

Programming Language 의 풍부한 능력을 제대로 사용하지 못하고, 제한된 기능만 가지고서는 Algorithm 의 표현도 제한됩니다.

또한 source 를 보면 제가 보기에 중복되었다고 생각되는 부분이 많습니다.
우선 Initialize 와 DFS 는 중복이 너무 많습니다.
저라면 꼭 필요한 Initialize 는 main 에서 처리하고 DFS 하나로 통일했을 겁니다.

swapNodeValue 에서도 역시 중복이 너무 많아보이고요.
사실 저도 이런식으로 puzzle 을 이동시키려다 만든 것이 coordinate 와 available_direction 이었습니다.

이차원배열을 행렬위치표기를 사용해서 blank 의 위치에 direction 을 더해서 새로운 위치를 만들고, 값을 바꾸는 거죠. direction 의 반대방향검증도 편할테구요.

value 의 값을 복사하거나 비교할 때는 함수를 사용하심이 좋을 거라고 생각합니다. 문자배열로 만든다면 strncpy, strcmp, 정수배열을 그대로 쓰신다면 memcpy, memcmp...

참고로 memcpy 와 memcmp 는 쌍으로 사용하심이 좋습니다. element 단위 복사와 element 단위 비교또한 쌍으로 쓰셔야 합니다.

만약 element 단위로 복사하고, memcmp 로 비교하시면 padding bit 로 인해 다른 결과가 나올 수 있습니다.

시간여유가 있으시다면(아마 없겠지만... -_-... 숙제제출하고 나서도 시간을 내셔서 하신다면) 구조적인 측면을 간소화시키기 위해 source 를 이리저리 뒤집어보는 것이 공부에 좋을 거라고 생각합니다.

또한 Programming Language 를 좀더 자세히 공부하시고, 표준 library 의 기능을 활용하시기 바랍니다.

제가 생각하기에는 학부과정에서 필요한 C library 는 stdio.h, stdlib.h, string.h, ctype.h, math.h 에 다 들어있다고 생각됩니다.

음.. 지금보니 memcpy, strncpy 도 필요없이
*childNode[i] = *pNode[pCount];
하신 후 변경되는 정보만 고쳐도 되겠군요.

솔직히 저 역시 쥐뿔도 모릅니다.

BBS 에 제 이름으로 검색해보시면 헛소리만 늘어놓고 있던 것을 알 수 있습니다.

또한 저 역시 memcmp 를 사용한 적이 없습니다...(-_-)

기타 여기에 적어 놓은 C 언어에 대한 것도 1년 전만 해도 몰랐던 것이었고, 또한 Algorithm 수업에서 동일한 문제를 풀어본 적이 있었기에 다행히 답변을 드릴 수 있었던 것 같습니다.

겸손하신 모습이 보기 좋네요.
저도 좀 자중이 필요할 듯... (-_-)

1% 도 못쓴다고 하셨지만 조금만 노력하시면 금방 실력이 좋아지실 것 같습니다.

어쩌면 그 이후에 왜 이렇게 별 것도 아닌 것 가지고 낑낑댔지라는 생각이 드실지도...(제가 그랬었거든요... ^^)

그럼 열심히 하세요!!!

그리고 모르시는 것이 있으면 또한 물어보셔도 좋습니다...
원래 community 라는 것이 정보의 공유이니까요.
열심히 노력하시고, 그 이후에 물어보시는데다 그냥 숙제 해달라는 것도 아니니까요.
(단 숙제라는 티는 내지 않음이 좋을 듯... -_-)

RAND 계열의 모든 함수는 중복을 피할 수 없습니다. 일단 순서대로 나열해 놓고
섞어주는 함수를 RAND로 돌려서 순서를 바꾼 후 순서대로 처리하는게 옳습니다.
원하시는게 랜덤한 '숫자'인지 랜덤한 '순서'인지가 확실해지면 고민꺼리는
아니라고 생각됩니다. ^^;

malloc 함수가 void* 형을 return한다는 것을 알고 있을 것입니다.
저는 embedded 환경에서 주로 c로 coding을 합니다만 void*형을 casting을 해주지 않는 것이 더 좋다는 이야기는 금시초문입니다.
요즘 compiler가 좋아서 void*형을 malloc에서 자동 casting한다고 해서 void* 가 casting없이 사용가능하다고 생각하면 오산입니다.

#include<stdlib.h>
#include<stdio.h>

int main(void) {

	int* i;
	void* a;
	int	j;

	i = malloc(10);

	i[9] = 8;
	
	j = 4;	
	
	a = &j;
	
//	printf("a[0] = %d\n", *a);
	printf("a[0] = %d\n", *(int *)a);
	printf("a[0] = %d\n", i[9]);
	

	return(0);

}

malloc은 error가 없습니다. (심지여 sizeof(int)를 뺐는대도 gcc에선 잘 동작하는군요.)
하지만 다른 부분에서 *a의 사용은 invalid void expression이란 error를 발생시킵니다. void*를 다른 형태로 사용할려면 반드시 casting되어야 합니다.
다른 compiler에서 error를 발생시킬 여지가 있는 비표준 코드는 사용하지 않는 것이 좋습니다.

당연히.. i[9]는 *(i + 9)이고, i는 pointer to int 이니까

i = malloc(sizeof(int) * 10);

i = (int *)malloc(10); 

void *generic_ptr;
int *int ptr;

generic_ptr = int_ptr;        /* OK */
int_ptr = generic_ptr;        /* OK */