그래프3 그래프 탐색 - DFS vs BFS 1. 경로 찾는 문제가 나온다면..?방법은 2개가 있다1) 더 이상 탐색할 노드 없을 때 까지 탐색해본다. 더 이상 탐색할 노드 없으면 최근 방문 노드로 되돌아가서 가지 않은 노드 방문한다2) 현재 위치에서 가장 가까운 노드 모두 싹 돌고, 다음 노드로 넘어감. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문이게 뭐냐? 각각 깊이 우선 탐색, 너비 우선 탐색임이해가 쉽도록 아래 그림을 확인해보자.1.1. 깊이 우선 탐색 1.2. 너비우선탐색2. 코테 풀 때!!!탐색은 해야하는데 최단 경로 구하는 거 아니면 DFS 쓰면 됨최단 경로 찾는다? BFS 갈겨~~~~ 2025. 2. 4. 그래프 1. 그래프란?노드(정점,vertex)랑 간선(edge)을 이용한 비선형(일렬이 아닌 것) 데이터 구조데이터 관계 표현 시 사용함방향성 : 간선은 방향이 있을 수도 없을 수도 있음없으면 무방향 그래프 undirected graph있으면 방향 그래프 directed graph둘다 서로 가리키는 간선도 있음가중치 : 흐름의 정도가중치가 있는 그래프 : weight graph순환 : 다시 돌아오는 경로있으면 순환 그래프 cycle graph없으면 비순환 그래프 acyclic graph 2. 그래프 구현은 어떻게?구현할 때 인접행렬(adjacency matrix), 인접리스트(adjacency list) 두가지 방법이 있음"송파역에서 석촌역으로 유동인구가 5000명 발생" 을 구현해보자데이터 담고 있는 노드 .. 2025. 2. 4. [자료구조] DFS와 BFS DFS 와 BFS란?DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 탐색 알고리즘그래프의 모든 노드를 탐색하는 방법임두 알고리즘은 탐색의 순서와 방식에서 차이 있음시간복잡도는 DFS/ BFS 동일함-> 왜냐? 모든 조건 내 모든 노드를 검색하니까--> But, 최단거리 구할 때는 BFS가 유리함 1. DFS (Depth-First Search)- 개념: DFS는 깊이 우선 탐색한 노드에서 시작하여 다음 분기로 넘어가기 전에!!해당 분기를 따라 최대한 깊이 내려가며 탐색하는 방법 - 특징: 스택 (Stack) 사용재귀 호출을 사용할 수 있음한 경로를 끝까지 탐색한 후, 다른 경로를 탐색 2. BFS (Breadth-First Search)- 개념:BF.. 2024. 8. 2. 이전 1 다음
