[깊이 우선 탐색 DFS]1 [깊이 우선 탐색 DFS] 백준 11724 [깊이 우선 탐색 DFS]은 그래프 완전 탐색 기법 중 하나로 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해 다시 탐색하는 알고리즘이다. 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로를 유의해야 한다! 깊이 우선 탐색은 단절점 찾기, 사이클 찾기, 위상 정렬 등에 응용하여 문제를 풀 수 있다. 깊이 우선 탐색의 핵심 이론 DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현하겠다. 그리고 DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하여 설명하겠다. 1.DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 원본 그래프를 인접리스.. 2024. 2. 27. 이전 1 다음
notcherry
