그래프 탐색 알고리즘

그래프: 여러 개체들이 연결되어 있는 자료구조
탐색: 특정 개체를 찾기 위한 알고리즘

대표 유형: 경로 탐색, 네트워크, 조합 만들기
DFS, BFS는 둘 다 탐색 알고리즘이라서 둘 중 어느 것을 써도 답은 나온다!

🔍 깊이 우선 탐색 (DFS, Depth-First-Search)

• 개념: 최대한 깊이 내려가 탐색하고, 더 이상 갈 곳이 없을 때 옆으로 이동
• 자료구조: Stack 또는 재귀 함수 사용

🔍 너비 우선 탐색 (BFS, Breadth-First-Search)

• 개념: 최대한 넓게 이동하여 탐색하고, 더 이상 갈 곳이 없을 때 아래로 이동
• 자료구조: Queue나 LinkedList 사용

📊 비교 요약

항목	DFS	BFS
구현 난이도	간단	큐 사용 필요
유리한 상황	경로 찾기, 백트래킹 문제 등	최단 거리 문제
시간 복잡도	O(V + E)	O(V + E)

(V: 정점 수, E: 간선 수)

---

🧠 BFS 구현

중복 방문을 피하기 위해서 주로 Queue를 사용해서 구현

적용 문제

• 미로 탐색
• 최단 거리
• 물 퍼뜨리기, 감염 확산
• 레벨 탐색 (트리의 depth 구하기)

순서 요약

1. 준비 작업
   a. 큐(Queue) 생성
   → BFS는 가까운 노드부터 차례대로 탐색하므로, 선입선출 구조인 큐가 필요
   b. 방문 배열 생성 ( visited[] )
   → 이미 방문한 노드를 중복해서 다시 큐에 넣지 않도록 하기 위해 필요
   → 그래야 무한 루프를 방지하고, 최단거리 보장이 가능

2. 시작 노드를 큐에 넣고 방문 표시
   탐색을 시작할 노드를 queue.add(start)로 넣고,
   visited[start] = true로 방문 처리

3. 큐가 빌 때까지 반복
   while (!queue.isEmpty()):
   a. queue.poll()로 현재 노드 꺼냄
   → 이 노드를 기준으로 인접 노드들을 탐색
   b. 현재 노드의 인접 노드들을 하나씩 보며 아직 방문하지 않았다면,
   → queue.add(next)로 큐에 추가
   → visited[next] = true로 방문 표시