개발스토리

그래프 탐색 ■ 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 탐색 과정 EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지에 대한 탐색 과정 DFS(깊이 우선 탐색) ■ root node나 다른 임의의 노드에서 시작하여 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법 ■ 넓게 탐색하기전에 깊게 탐색하는 것 ■ DFS가 BFS보다 좀 더 간단함 DFS(깊이 우선 탐색)의 특징 ■ 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다. ■ 그래프 탐색의 경우 어떤 노드를 방문했었는 지 여부를 반드시 검사해야 한다. ■ DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스..