알고리즘:등고선법을 통한 최단경로 찾기
2014. 3. 27. 09:52ㆍ프로그래밍/알고리즘
등고선 알고리즘
길 찾기 알고리즘 중 하나로 등고선 알고리즘을 이용하면 길의 유무와 최단 거리를 찾아 낼 수 있다.
알고리즘
1. 시작 점과 도착 지점을 정한다.
2. 도착 지점 주위의 이동가능한 길에 번호를 적는다.
3. 번호를 입력한 곳 주위의 이동 가능한 길에 번호를 적는다.
4. 1~3 반복하여, 시작 지점에 도달하면 종료. 시작지점에 도달하지 못하고 더 이상 길이 없는 경우 길이 없는 것으로 판단.
소스코드
프로그램 첨부
설명 및 주의사항
가. 프로그램
- 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 |