목록Algorithm/DFS (1)
Jun's Development Journey
[Algorithm] DFS 기법 설명 및 활용
1. DFS(Depth First Search) - 깊이 우선 탐색 - 그래프 전체를 탐색하는 방법 중 하나 - 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법 - 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방법 - 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 함 - 완전 탐색, 길찾기, 그래프 순회 등등에 사용 2. 예시 문제 문제) www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 ..
Algorithm/DFS
2021. 3. 1. 22:34