[Java- Algorithm] 너비 우선 탐색법(BFS과 큐(Queue)

너비 우선 탐색법(BFS)이란?

 

File:Breadth-First-Search-Algorithm.gif - Wikimedia Commons

위의 GIF는 BFS이고 아래는 DFS이다. 차이점을 먼저 확인해보자.

https://en.m.wikipedia.org/wiki/File:Depth-First-Search.gif

 

✅공통점
방문 여부 확인을 통해 한 번 지나간 노드는 다시 방문하지 않는다.



✅차이점

DFS는 정점(1)에서 연결된 노드를 순서대로 아래로 내려가며 다음 노드가 없는 경우 다음 연결된 노드로 이동하며 탐색한다.
또한 재귀호출 및 스택방식으로 코드를 구현한다.

BFS는 같은 레벨(가장 가까운 노드)에서 검색을 시작하며 최단 거리를 탐색한다.
큐 방식으로 코드를 구현한다.
배열에서 사용하는 경우 방향 데이터를 이용해 시작점의 범위를 넓혀가면서 탐색한다.
DFS는 무한한길이를 가진 경로가 존재하고 목표는 다른 경로에 있을 경우 해결하지 못하지만 BFS는 모든 경로를 동시에 탐색하기 때문에 다른 경로의 목표에 접근이 가능하다.


하지만 BFS도 경로의 길이가 매우 길고 목표로 하는 노드가 가장 마지막에 있다면 메모리를 많이 요구하고, 효율도 좋지 못한 방법이 됩니다.

 

 

예시 

 

Do it !자바 알고리즘

 

 

Queue방식으로 데이터가 삽입되는 것을 아래의 그림에서 확인할 수 있습니다.

Do it !자바 알고리즘

 

이 내용을 공부하고나서 백준문제를 풀어볼건데요 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

풀이도 곧 포스팅하겠습니다!