그래프 탐색2 DFS (Depth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법 Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 DFS1. DFS란Depth-first search, 깊이 우선 탐색그래프 탐색 종류 중 하나Stack 또는 재귀 함수 사용, Queue 미사용!재귀 함수는 백트래킹 알고리즘에서도 사용!2. 재귀함수란자기 자신을 다시 호출하는 함수# 예시def my_function(a): c = a + 1 if c 주의: 재귀 함수가 종료되는 시점을 반드시 명시해야 됨재귀 함수의 깊이가 .. 2024. 11. 8. BFS (Breadth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 BFS1. BFS란Breadth-first search, 너비 우선 탐색그래프 탐색 종류 중 하나Queue 사용, Stack 미사용!2. 준비하기1) 아이디어시작점에 연결된 Vertex 찾기 찾은 Vertex를 Queue에 저장 Queue의 가장 먼저 것 뽑아서 반복2) 시간 복잡도O(V+E)3) 자료구조검색할 그래프 방문여부 확인(재방문 금지) Queue: BFS 실행3. 연습 문제:.. 2024. 11. 4. 이전 1 다음
