반응형 Programming/Algorithm35 슬라이딩 퍼즐 - A* 알고리즘으로 풀기 이제, 최종적으로 구현을 한 프로그램입니다. A* 알고리즘을 적용하기 위해서 A* 용 자료구조를 설계했습니다. A* 알고리즘에서는 기본적으로 힙 구조를 사용하며, 검색을 빨리 하기 위해서 해시테이블을 이용합니다. 그래서 두 가지 모두를 결합한 형태의 자료구조를 만들었습니다. [PuzzleNode 자료구조] class PuzzleNode : public PQueue::Node { public: PuzzleNode(char *csquares, int cEmptySquare, int cvalue) : value(cvalue), visited(false) { squares = csquares; emptySquare = cEmptySquare; est = 0; for( int i = 0 ; i < numSquar.. 2015. 2. 18. 슬라이딩 퍼즐 - 움직임 슬라이딩 퍼즐의 자료구조를 잡는 것이 필요한데요. 제 경우에는 단순 배열로 작성을 했습니다. char *squares; int emptySquare; squares 변수는 1차원 배열로, 2차원 배열을 따로 복잡하게 구성하지 않았습니다. 사실 C/C++ 언어에서 단순 배열은 모두 1차원 배열로 인식을 합니다. 형식만 2차원, 3차원이 되는 것 뿐이죠. emptySquare는 어떤 칸이 비어있는지를 나타냅니다. 해당 칸은 0이란 값을 적게 됩니다. 이 자료구조를 토대로 움직임 함수를 구현한 것입니다. bool Move(PuzzleParams *param, eMove move) { int newEmptySquare = Move(param->squares, param->rows, param->cols, par.. 2015. 2. 18. 슬라이딩 퍼즐 풀기 - 기본편 어렸을 때, 한번쯤은 다들 해보았을 법한 퍼즐입니다. 일반적으로 4x4 퍼즐이라고도 하고, 그림 퍼즐이라고도 합니다. 하지만 퍼즐이란 말은 무언가 풀어볼 수 있는 형태의 게임을 다 지칭하는 것이라서요. 슬라이딩 퍼즐이라고 한정지어서 이야기하는 것이 맞을 듯 합니다. 4x4 슬라이딩 퍼즐 보통 많이 있는 퍼즐은 4x4 퍼즐로 위와 같이 숫자가 1부터 15까지 써 있는 형태이거나 그림이 있는 경우입니다. 4x4 그림 퍼즐 퍼즐 자체가 어렵지 않기 때문에, 하다보면 퍼즐을 맞출 수가 있습니다. 보통은 빈칸이 있는 곳과 가장 먼 줄부터 맞추어 나가는 것이죠. 맨 마지막 두줄은 돌리면서 회전하는 것을 생각해서 위치를 맞추면 됩니다. 그런데 최적의 해를 구할려면 어떻게 될까요? 슬라이딩 퍼즐은 모든 경우의 수를 따.. 2015. 2. 13. A* 알고리즘을 이용한 하노이 타워 풀기 A* 알고리즘을 이용해서 일반적으로는 길찾기를 많이 합니다. A* 알고리즘은 적절한 에너지 함수만 제공해준다면, 최적의 해를 적은 노드 탐방으로 찾을 수 있는 장점이 있습니다. 그러나 적절한 에너지 함수를 제공할 수 없는 경우에는, A* 알고리즘은 상당히 많은 시간을 소모할 수 있고, 또한 최적의 해를 찾을 수 없을 수도 있습니다. 1) 에너지 함수가 실제 소요되는 것보다 상대적으로 너무 적을 때에는 많은 노드를 탐방하게 됩니다. 2) 에너지 함수가 실제 소요되는 것보다 더 많을 가능성이 아주 조금이라도 있다면, 최적의 해를 찾는다는 보장을 할 수 없습니다. 제가 A* 알고리즘을 조금 더 관심있게 보고 있는 것은 바로 2)항 때문입니다. 게임 AI 로직에서 최적의 해를 꼭 찾아야한다고 볼 수 없습니다. .. 2014. 12. 11. A* 알고리즘을 위한 우선순위 큐 구현 알고리즘 그래프 이론을 들어가면, 가장 끝판왕은 역시나 A* 알고리즘이라고 생각합니다. A* 알고리즘은 게임 프로그래밍에서도 많이 쓰이는 기법이니, 알아두는 것이 좋지 않을까 하네요. A* 알고리즘을 적용할 때, 방문해야할 노드 수가 많을 때, 속도에 영향을 미치는 부분은 두가지가 있습니다. 첫번째는 가장 작은 에너지 함수값을 갖는 노드를 찾는 것입니다. 두번째는 방문한 셋에 포함되어 있는지 찾는 것입니다. 제 경우에는 작은 에너지 함수값을 갖는 노드를 찾는 것은 힙을 이용한 우선순위 큐를 사용합니다. 힙을 이용하게 되면, 삽입과 삭제의 경우 \(O(\log n)\)의 점근적 시간이 필요합니다. 선형으로 찾는 것보다 훨씬 빠르게 삽입 삭제를 할 수 있습니다. 방문한 셋에 포함되어있는지 검사하는 방법은 해.. 2014. 12. 8. 하노이 타워 알고리즘을 하다보면, 자기호출함수 부분을 배울 때, 하노이 타워에 관련되어서는 한번쯤 이야기가 됩니다. 하노이 타워는 대표적인 재귀적 관점이 들어가 있습니다. (사진출처 : 위키피디아) 하노이 타워가 재귀적 관점이 들어가는 가장 큰 이유는, 작은 디스크 위에 큰 디스크가 올라갈 수 없다는 이유때문입니다. 위 그림에서 첫번째 기둥에 있는 8개의 디스크를 가운데 기둥으로 모두 옮겨야 한다고 하면, 가장 큰 디스크는, 위에 있는 7개의 디스크를 맨 오른쪽 기둥으로 옮기고 나서야 옮길 수 있습니다. 가장 큰 디스크를 가운데 기둥으로 옮긴다음, 맨 오른쪽에 있는 7개의 디스크를 가운데 기둥으로 옮기면 됩니다. 그래서 n개의 디스크를 옮긴다면, 다음과 같이 재귀적 알고리즘을 적용할 수 있습니다. 1) n-1개의 디.. 2014. 12. 5. 이전 1 2 3 4 5 6 다음 728x90
