목록Breadth First Search (1)

Seung's Learning Record

너비 우선 탐색 / BFS

BFS(Breadth First Search) BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다. 시작 정점을 방문한 후, 인접한 정점들을 우선 방문하는 방법이다. 해당 그래프의 방문 순서가 저럴 경우, 큐에 값이 들어가고 나가는 순서는 다음과 같다. push(0) -> pop(0) -> push(1), push(2) -> pop(1) -> push(3) -> pop(2) -> push(4) -> pop(3) -> pop(4) BFS구현 이론 BFS 구현을 위해서는 큐를 사용해야 한다. 쉬운 이해를 위해 빨간색,파란색이 섞여있는 2차원 배열에서 파란색 칸만을 탐색하는 알고리즘을 작성하는 과정을 예로 들어 구현 플로우를 대강 정리해보자. 시작 좌표(0,0)를 방문 표시 후,..
알고리즘 2023. 11. 9. 18:53
이전 Prev 1 Next 다음