1. 그래프 탐색
- 그래프는 노드 (Node)와 간선 (Edge)으로 이루어진 자료구조이다.
- 그래프 탐색은 그래프에서 특정 조건을 만족하는 노드를 찾거나, 모든 노드를 방문하는 데 사용한다.
- BFS와 DFS는 가장 일반적인 그래프 탐색 알고리즘이다.
2. BFS (Breadth First Search)
- 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘
- 특정 노드에서 인접한 노드를 모두 방문한 다음, 다음 레벨의 인접 노드로 이동하는 방법
- 자료구조 큐(Queue)를 사용하여 구현한다.
- BFS는 재귀적으로 작동하지 않는다.
- BFS는 어떤 노드의 방문 여부를 반드시 검사해야 한다.
- DFS는 무한한 길이를 가지는 경로에 도달했을 시 탐색 목표가 현재 경로에 있지 않다면 무한 루프에 빠질 수 있지만 BFS는 모든 경로를 동시에 진행하여 탐색이 가능하다.
BFS 탐색 과정
- 그림으로 보는게 좋겠다.
- 시작 정점으로부터 깊이가 1인 모든 노드를 방문한다.
- 노드 방문 시에는 반드시 방문 여부를 검사한다.
- 인접한 모든 노드를 확인하여 큐(Queue)에 넣는다.
- 다음 깊이(2)의 모든 노드를 확인, 방문 체크, 큐 삽입을 반복한다.
- 마지막 노드에 도달하여 더 이상 방문할 곳이 없다면 탐색을 마친다.
시간 복잡도
- 인접 행렬 그래프 : O(N^2)
- 인접 리스트 그래프 : O(N + E)
3. 관련 문제
풀어보겠다,,,
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [알고리즘] [9] 연결리스트 (0) | 2024.02.05 |
|---|---|
| [알고리즘] [8] 부분 집합 (1) | 2024.02.01 |
| [알고리즘] [7] 조합 (0) | 2024.01.31 |
| [알고리즘] [6] 완전탐색, 순열 (1) | 2024.01.30 |
| [알고리즘] [5] 재귀 (0) | 2024.01.29 |
| [알고리즘] [4] 문제 해결 (1) | 2024.01.29 |
| [알고리즘] [2] 병합 정렬 (0) | 2024.01.14 |
| [알고리즘] [1] 힙 정렬 (3) | 2023.12.04 |
