Notice
반응형
Recent Posts
Recent Comments
Link
Today
Total
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
Archives
Tags more
관리 메뉴

목록[깊이 우선 탐색 DFS] (1)

notcherry

[깊이 우선 탐색 DFS] 백준 11724

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