[알고리즘]깊이우선탐색(DFS)

깊이우선탐색 깊이우선탐색은 더 이상 탐색할 정점이 없을떄 까지 간선을 계속 타고 갑니다. 더이상 탐색할 정점이 없으면 가장 최근에 방문한 정점 중, 탐색할 정점이 남은 정점에서 탐색을 계속 진행 합니다. 다시 정리해보면, 구현을 할때 핵심적인 부분은 아래와 같습니다. 1. 탐색할 정점이 없을때까지 간선을 타고 내려갈 수 있어야 합니다. 2. 가장 “최근에” 방문한 정점을 알아야 합니다. 3. 이미 방문한 “정점”인지 확인 할 수 있어야 합니다. 이를 적용해서, 아래 그래프를 깊이우선탐색 해봅시다. 인접행렬로 그래프 표현 동작 자체를 이해하는건 쉬운데, 구현하는 입장에서 생각하면 직관적이지 않습니다. 더 이상 연결된 정점이 없을때, 가장 최근 방문한 정점에서 방문하지 않는 정점을 어떻게 찾을 수 있을까요? STACK을 활용하면 이를 쉽게 해결할 수 있습니다. STACK은 기본적으로 선입후출(First In Last Out)구조를 가지고 있습니다. 특정 정점 방문시, 방문여부를 체크하고...

원문링크 : [알고리즘]깊이우선탐색(DFS)