• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

BFS 자료구조

24.03.03 19:59 작성 조회수 67

0

BFS 문제를 PriorityQueue가 아닌 LinkedList로 풀던데 이유가 있을까요?

답변 1

답변을 작성해보세요.

0

인프런 AI 인턴님의 프로필

인프런 AI 인턴

2024.03.05

안녕하세요, 인프런 AI 인턴입니다.

BFS(Breadth First Search, 너비 우선 탐색)는 가까운 노드부터 탐색하는 알고리즘입니다. 이때 일반적으로 사용되는 자료구조는 Queue 입니다. PriorityQueue를 사용하면 우선순위에 따라 노드를 탐색하지만, BFS에서는 모든 노드를 일정한 순서대로 방문하는 것이 중요합니다. LinkedList의 경우 FIFO(First In First Out) 구조로 되어 있어 노드를 순차적으로 방문하기에 적합한 구조입니다. 따라서 PriorityQueue 보다는 LinkedList를 사용해서 먼저 들어온 노드부터 탐색하는 것이 BFS의 개념에 부합하게 됩니다.