Algorithm

Algorithm 그래프 탐색 SP(Shortest Path) 단일 출발점에서 단일 목적지까지 최단 경로를 찾는 알고리즘 DFS 용도 : 경로가 있는지 확인할 때 사용 가능 자로구조 : stack 방법 : 시작 node를 stack에 넣는다. stack이 모두 빌때까지 아래 동작을 반복한다. stack의 top을 현재 node로 설정한다. 현재 node를 ‘visited’ 처리하고 stack에서 제거한다. 다음으로 이동할 node가 있는지 확인한다. 다음으로 이동할 node ‘A’가 있다면, 현재 node에서 그다음에 탐색할 방향을 stack에 push하고, node ‘A’도 stack에 push한다. 더이상 갈 곳이 없으면 현재 node의 visited 처리를 복원한다. 최종 목적지에 도달한 경우를 모아 결과값을 비교한다. 예시 : BFS 용도 : 최단경로 탐색에 사용 가능 자로구조 : queue 방법 : 시작 node를 queue에 넣는다. queue가 비거나 목적지에 도달할 때 까지 아래 동작을 반복한다. queue의 front를 pop 하여 현재 node로 설정한다. 현재 node에서 이동 가능한 node가 있는지 확인하고, 이동 가능하다면 모두 queue에 push한다. queue에 push하면서 해당 경로는 ‘visited’ 처리를 한다. (주의) queue에 넣으면서 visited 처리를 하고, queue에 넣기전에 방문 여부를 판단해야 메모리 부족을 예방할 수 있다. SSSP (Single Source Shortest Path) 단일 출발점에서 모든 node까지 최단 경로를 찾는 알고리즘 ...