NineTwo meet you

DFS(depth-first search)란? 그래프 이론에서 많이 사용되는 탐색 알고리즘 중 하나다. 현재 정점에서 인접한 간선들을 하나씩 점검하다 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 탐색 알고리즘이다. 이전까지 거쳐온 정점을 기억하기 위해서 재귀를 사용한다. 또한 그래프의 모든 정점이 간선을 통해 연결되어 있다는 보장이 없기 때문에 그래프의 전체 구조를 파악하기 위해서 DFS로 풀 수 있는 유명한 문제를 살펴보겠습니다. 위상 정렬(topological sort) 그래프의 순서를 정렬하기 위한 방법이다. 각 정점의 의존 관계를 간선으로 표현한 의존성 그래프(dependency graph)의 순서를 나타내기 위해 사용된다. 이 그래프의 가장 큰 특징은 사이클이 없..