탐색1 DFS(Depth-First Search; 깊이우선탐색) 그래프 탐색(Graph Search)이란?어떤 그래프에서, vertex s로부터 v까지의 path가 존재하는지 알아내는 것이다.ex) 특정 도시에서 한 도시로 갈 수 있는가? / 나와 특정 사람 간에 페이스북 친구들을 매개로 이어질 수 있는가? 등DFS(Depth-First Search; 깊이 우선 탐색)미로 찾기DFS에 대해 알아보기 전에, 여러 통행로(passage)와 교차로(intersection)들로 구성된 미로 속에서 길을 찾는 모습을 떠올려 보자. 미로에서 길 찾는 문제를 해결하는 방법으로 Tremaux exploration이라는 것이 있는데, 과정은 다음과 같다.▪︎ 아직 방문하지 않은 통행로 중 아무 곳이나 가본다. 처음으로 지나가는 통행로에는 길을 따라 선을 그어 놓는다.▪︎ 방문한 모든.. 2019. 1. 7. 이전 1 다음
