#️⃣ 어떤 브랜치인가요?

• basic
• baekjoon
• other:

BFS 구현하기

기본부터 돌아가는 마음으로 기본적인 BFS 에 대한 구현을 진행했습니다.

BFS의 핵심은
현재 위치를 처리한 뒤, 그 주변 노드들을 먼저 탐색하도록 관리하는 것입니다.
즉, 깊게 들어가기보다는 너비 방향으로 확장해 나가는 방식으로
주변 애들부터 탐색을 해야하기에 다음에 처리할 일을 저장해둘 저장 공간이 필요해 선입 선출이 가능한 Queue를 사용하는 것이 핵심.

크게 핵심으로는

1. Queue를 통한 탐색 순서 관리
   • 흔히 구현체로 LinkedList를 쓰지만 이후 우선 순위가 있는 BFS 의 경우 PriorityQueue를 사용
2. 주변 노드 탐색 로직
   • 흔하게는 상하좌우 탐색을 하게함 본 구현에선 하우 만 가능하게.
3. 중복 방문 방지 처리
   • 한번 방문한 노드를 처리해주지 않으면 불필요한 연산이 늘어나거나 무한루프에 빠질 수 있음으로 visted 배열을 통해 해결
4. 종료 조건 또는 결과 판독

이런 특징으로 구현을 하게 됩니다.

4가지로 이루어져 있습니다.