Programmer's Progress

이전에 C언어로 작성한 랜덤 미로 생성 알고리즘은 성공적이었다. 정상적으로 원하는 형태의 미로가 구현되는 것을 확인할 수 있었다. 그런데, 마침 이번에 친구가 웹 그래픽스 수업을 들으면서 미로를 탈출하는 간단한 게임을 구현하고자 하는데 미로를 어떻게 하면 만들 수 있을지 그 조언을 구하였고, 이에 웹에서 사용할 수 있도록 Java Script 버전으로 재설계하여 그 소스코드를 전달하기로 했다. 아래는 이것을 그래픽으로 출력한 예제를 구현한 것이다. 버튼을 누르면 미로가 무작위로 생성이 되며, 빨간색 사각형에서 파란색 사각형으로 이동하는 것이 목표다. $(document).ready(function () { var wall = '-1', start = '0', end='1', empty = '2'; var..

BFS탐색 알고리즘을 공부하면서 미로를 탈출하는데 걸리는 최소비용, 거리, 최단 경로를 출력하는 문제를 여러 번 풀어보고, 또 내 지식으로 만들고자 복습하기도 했지만, 한 가지 아쉬웠던 점은 이러한 테스트 케이스로 사용할 미로가 그렇게 많지 않았다는 것이다. 그렇다고 미로를 수작업으로 만들수도 없는 일이었다. 그래서 미로를 어떻게하면 생성할 수 있는지 검색해본 결과, 여러 알고리즘이 있었지만 그중 BFS 탐색과 짝을 이룬다 할 수 있는 DFS 탐색으로 미로를 생성하는 알고리즘을 직접 구현해보았다. BFS탐색이 방문여부 배열을 이용하여 계속 새로운 노드를 방문하면서 Queue에 추가하고, 다시 탐색하는 과정을 반복하는 알고리즘이라면, DFS는 재귀적으로 탐색하는 방식이라고 할 수 있겠다. 그렇다면 DFS탐..