너비우선탐색 기반 최단 거리 예제 풀이

Program Lang./Algorithm 2017. 5. 31. 13:41

1. 목적

공부한 내용 다음에 다시 복습하기 위해서 여기에 정리. 알고리즘 동작 원리는 설명은 생략.

여기 (http://blog.eairship.kr/268) 블로그에 정리된 내용 중에 최단 거리 탐색 문제를 내 나름되로 짜 봤다.


2. 코드 설명

너비 우선 탐색 기반은 비선형 탐색의 한 종류로 Queue 기반으로 Stack 기반의 깊이기반 탐색에서 10만번 이상을 수행 시에 Stack Overflow에 대한 제약 사항을 해결할 수 있는 하나의 방식이다.



3. 실행 결과

깊이 우선 순위 탐색과 달리 Path가 나눠져서 도달하지는 않는다.


end of map : min = 12 
-1 -1 -1 -1 -1 
 0  0  0  0 -1 
-1 -1 -1 -1 -1 
-1  0 -1  0  0 
-1 -1 -1 -1 -1 

최단거리 : 12 


: