BFS(너비 우선 탐색)
- 그래프를 완전 탐색하는 방법 중 하나
- 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
- 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
- 특징 : FIFO 탐색, 큐 자료구조를 이용한다.
- 시간 복잡도는 O(V + E)이며, 여기서 V는 노드 수, E는 엣지 수를 말한다.
BFS 과정
- BFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화한다.
- 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입한다.
- 큐 자료구조에 값이 없을 때까지 반복한다.
문제 풀이
https://yurison.tistory.com/555
[백준/자바] 1260 - DFS와 BFS
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static ArrayList[] arr; static boolean[] visited; public static void main(String[] args) throws IOException { BufferedReade
yurison.tistory.com
https://yurison.tistory.com/556
[백준/자바] 2178 - 미로 탐색
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int[] dx = {0, 1, 0, -1}; static int[] dy = {1, 0
yurison.tistory.com
https://yurison.tistory.com/557
[백준/자바] 1167 - 트리의 지름
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static boolean[] visited; static int[] distance; static ArrayList[] arr; public static void main(String[] args) throws IOEx
yurison.tistory.com
'공부 기록 > 알고리즘' 카테고리의 다른 글
| Do it! 알고리즘 코딩테스트 with JAVA - (16) 그리디 알고리즘 (0) | 2023.08.08 |
|---|---|
| Do it! 알고리즘 코딩테스트 with JAVA - (15) 이진 탐색 (0) | 2023.08.07 |
| Do it! 알고리즘 코딩테스트 with JAVA - (13) DFS(깊이 우선 탐색) (0) | 2023.08.04 |
| Do it! 알고리즘 코딩테스트 with JAVA - (12) 기수 정렬 (0) | 2023.08.03 |
| Do it! 알고리즘 코딩테스트 with JAVA - (11) 병합 정렬 (0) | 2023.08.03 |
