📚 목차
다른 페이지에서 추가 정리된 BFS
백준 1697 - 숨바꼭질
1. 너비 우선 탐색 (BFS)
1. 너비 우선 탐색
- 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
| 기능 |
특징 |
시간 복잡도(노드 수: V, 에지 수: E) |
| 그래프 완전 탐색 |
1.FIFO 탐색 |
|
- Queue 자료구조 이용 | O(V+E) |
2. 너비 우선 탐색의 핵심이론
- 원본 그래프를 인접 리스트로 표현하기
- 1부터 Queue에 Push한 후 방문 배열에 체크한다.
- 1을 pop하고 1에 인접한 노드 2, 3을 Queue에 Push하고 방문 배열에 체크한다.