깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, Breadth First Search))

BFS, DFS란 그래프의 탐색 기법으로

목적은 임의의 한 정점에서 시작하여 모든 정점을 방문하는 데 있다.

 

깊이 우선 탐색 - DFS(Depth-first search)

자식 노드를 우선적으로 탐색

즉, 아직 방문되지 않은 인접 노드(자식 노드)를 우선적으로 탐색

깊이 우선 탐색은 한쪽만 죽어라 파다가 더이상 팔 곳이 없으면 다시 돌아와서 다른 한쪽을 죽어라 파는 형식이다.

깊이 우선 탐색은 Stack을 통해 구현된다.

 

너비 우선 탐색 - BFS(Breadth-first search)=레벨 순회(level-order traversal)

코드링크 : BFS 코드 (tistory.com)

간선의 모든 가중치가 같을 때, 최단 거리를 구하는 알고리즘으로

시작 정점을 기준으로 가까운 정점을 먼저 방문한다.

방문 순서는 최단 거리에 영향을 끼친다.

형제 노드를 우선적으로 탐색

즉, 아직 방문되지 않은 이전 노드(부모 노드)의 인접 노드(현재 노드의 형제 노드)를 우선적으로 탐색

보통 너비 우선 탐색은 Queue를 통해 구현하여 선입선출의 원칙으로 탐색한다.

각 노드를 방문할 때 visit[y][x]=1로 변경해준다면,

visit[y][x]=1인 노드를 만날 때 continue; 해주는 방식으로 중복 방문을 회피한다.