[알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 0. 그래프 탐색 문제란? - 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)를 타고 이동할 수 있는 정점(Vertex, V)를 모두 찾는 문제 - 문제 해결법: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다. 1. 너비 우선 탐색(BFS)이란? - BFS (Breadth - First Search) - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 - 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것 - 두 노드 사이의 최단 경로 / 임의의 경로를 찾을 때 사용 2. 너비 우선 탐색의 특징 - 직관적 X.. 이전 1 다음