알고리즘:등고선법을 통한 최단경로 찾기

2014. 3. 27. 09:52프로그래밍/알고리즘

등고선 알고리즘

길 찾기 알고리즘 중 하나로 등고선 알고리즘을 이용하면 길의 유무와 최단 거리를 찾아 낼 수 있다.


알고리즘

1. 시작 점과 도착 지점을 정한다.

2. 도착 지점 주위의 이동가능한 길에 번호를 적는다.

3. 번호를 입력한 곳 주위의 이동 가능한 길에 번호를 적는다.

4. 1~3 반복하여, 시작 지점에 도달하면 종료. 시작지점에 도달하지 못하고 더 이상 길이 없는 경우 길이 없는 것으로 판단.


소스코드




프로그램 첨부

Recursive_Backtracking.exe



설명 및 주의사항

가. 프로그램

 - MFC GDI 사용

 - 메인 쓰레드에서 동작

 - 깜빡임 현상에 대한 별도의 처리를 하지 않음


나. 미로 만들기

 - Recursive BackTracking 알고리즘으로 생성

 - 미로 생성 과정을 보여주기 위해 Wait 함수를 사용함.

 - Wait 하는 만큼 미로 생성 시간이 걸리므로 미로가 클 수록 오래 기다려야 함.(15 크기 이상은 정신건강에 해로움...)


다. 길 찾기

 - 등고선법 사용

 - 시작 및 종료 위치 선택 필요.

 - 생성과정 안 보여줌.


라. 기타

 - 버그가 있을 수 있다...

'프로그래밍 > 알고리즘' 카테고리의 다른 글

알고리즘 : Postfix Notation  (0) 2014.05.20
알고리즘 : ConvexHull (Graham's Scan)  (4) 2014.05.01
알고리즘:Recursive Backtracking  (2) 2014.03.11
알고리즘:달팽이관  (0) 2013.04.16
알고리즘 카테고리 목적  (0) 2013.04.16