알고리즘/그래프 알고리즘
[Algorithm] BFS(너비 우선 탐색) 알고리즘 정리
Gyunny
2024. 9. 11. 00:20
728x90
반응형
BFS란?
BFS (Breadth-First Search)는 너비 우선 탐색 알고리즘으로, 그래프나 트리 구조에서 시작 정점으로부터 인접한 노드를 먼저 탐색하고, 그 다음 레벨의 노드들을 차례대로 탐색하는 방식입니다.
- 자료구조: Queue(큐)
- 탐색 방식: 현재 레벨의 모든 노드를 방문한 후, 다음 레벨로 진행
- 장점
- 최단 경로를 보장하며, 트리의 레벨 순으로 탐색이 가능합니다.
- 구현이 비교적 간단하며, 이해하기 쉽습니다.
- 트리/그래프의 레벨 탐색에 적합합니다.
- 단점
- 큐 사용으로 인해 많은 정점이 저장되면 메모리 사용이 많이 증가할 수 있습니다.
- 그래프가 넓거나, 간선이 많은 경우 비효율적일 수 있습니다.
BFS의 활용 예시
BFS는 실제 애플리케이션에서 다양한 문제를 해결하는 데 사용됩니다. BFS는 직관적인 탐색 방식은 큰 데이터 셋에서도 효율적인 탐색을 가능하게 합니다.
- 최단 경로 찾기: 지도나 게임 맵에서 출발 지점부터 목표 지점까지의 최단 거리를 찾을 때 사용
- 네트워크 탐색: 소셜 네트워크에서 친구 추천, 사용자 간 연결을 확인할 때 사용
- 웹 크롤러: 웹 페이지를 크롤링할 때 한 페이지에서 인접한 다른 페이지를 순차적으로 방문
- AI 및 로봇 탐색 문제: 미로 문제 또는 로봇 경로 찾기에서 자주 사용
- 바이러스 전파 시뮬레이션: 감염 범위 예측, 전염 모델링 등에 사용
BFS 동작 원리
BFS의 핵심은 큐를 사용해서 현재 정점에서 인접한 정점들을 먼저 탐색하는 것입니다.
다음은 BFS 알고리즘의 주요 단계입니다.
- 초기화 : 시작 노드를 큐에 넣고, 해당 정점을 방문 처리합니다.
- 큐에서 정점 꺼내기 : 큐에서 가장 앞의 정점을 꺼내 현재 탐색 중인 정점으로 설정합니다.
- 이웃 정점 탐색 : 현재 정점의 모든 이웃 정점을 확인하고, 방문하지 않은 정점들을 큐에 추가합니다.
- 반복 : 큐가 빌 때까지 위 과정을 반복합니다.
이 과정을 통해 BFS는 그래프의 모든 정점을 탐색하거나 특정 조건을 만족하는 정점을 찾을 때까지 탐색을 계속합니다.
BFS의 시간 및 공간 복잡도
- 시간 복잡도 : O(V + E) → V : 정점의 수 E : 간선의 수, 모든 정점과 모든 감선을 각각 한 번씩 탐색하기 때문
- 공간 복잡도 : O(V) → 최대 큐에 들어가는 정점의 수는 V
- 주의할 점
- 그래프가 매우 클 경우, 메모리 사용량이 크게 증가할 수 있습니다.
- 무방향 그래프에서 간선이 많을수록 큐에 더 많은 정점이 저장될 수 있습니다.
BFS의 장단점
자바 코드로 BFS 알고리즘 예제
예시 1 : 그래프 탐색 (인접 리스트 사용)
import java.util.*;
public class BFSGraphExample {
public static void bfs(List<List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.offer(start);
while (!queue.isEmpty()) {
int current = queue.poll();
System.out.print(current + " ");
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
public static void main(String[] args) {
// 그래프 초기화 (0~5번 노드)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < 6; i++) graph.add(new ArrayList<>());
// 간선 추가 (무방향 그래프)
graph.get(0).add(1); graph.get(0).add(2);
graph.get(1).add(0); graph.get(1).add(3); graph.get(1).add(4);
graph.get(2).add(0); graph.get(2).add(5);
graph.get(3).add(1);
graph.get(4).add(1);
graph.get(5).add(2);
System.out.println("BFS 탐색 순서:");
bfs(graph, 0);
}
}
// 출력결과
BFS 탐색 순서:
0 1 2 3 4 5예시 2 : 2차원 배열 미로 탐색
import java.util.*;
public class BFS2DArrayExample {
static int n = 5, m = 6;
static int[][] map = {
{1, 0, 1, 1, 1, 1},
{1, 0, 1, 0, 1, 0},
{1, 0, 1, 0, 1, 1},
{1, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 1}
};
static int[][] visited = new int[n][m];
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {x, y});
visited[x][y] = 1;
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int cx = curr[0], cy = curr[1];
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
visited[nx][ny] = visited[cx][cy] + 1;
queue.offer(new int[] {nx, ny});
}
}
}
}
}
public static void main(String[] args) {
bfs(0, 0);
System.out.println("최단 거리: " + visited[n - 1][m - 1]);
}
}
// 출력결과
최단 거리: 15두 예시 비교
| 항목 | 그래프 BFS (인접 리스트) | 2차원 배열 BFS (미로 탐색) |
| 사용 자료구조 | List<List<Integer>> | int[][] (배열) |
| 대표 사용 예시 | 소셜 네트워크 탐색, 경로 탐색 | 미로 찾기, 토마토 익히기, 영역 나누기 |
| 이동 방법 | 연결된 노드 순회 | 상하좌우 이동 (dx, dy) |
| 방문 기록 | boolean[] 배열 | in[][] 거리 겸 방문 기록 |
| 큐에 담는 값 | 노드 번호 (int) | 좌표 (int[] {x, y}) |
BFS와 DFS 비교
BFS와 DFS는 모두 그래프 탐색 알고리즘이지만, 탐색 방식에는 큰 차이가 있습니다. 메모리 사용량과 탐색 경로에서 차이가 있으므로 문제에 따라 적절한 선택을 해야 합니다.
| 항목 | BFS | DFS |
| 탐색 방식 | 너비 우선 | 깊이 우선 |
| 자료구조 | 큐(Queue) | 스택(Stack), 재귀 |
| 최단 거리 보장 | 가능 | 보장 X |
| 메모리 사용 | 큼 | 작음 |
| 응용 | 최단 경로, 친구 추천 | 백트래킹, 경로 추적 |
결론
- BFS는 그래프/맵 탐색의 기본이 되는 알고리즘입니다.
- 큐를 이용해 너비 우선으로 탐색하며, 최단 경로를 보장할 수 있다는 점에서 다양한 문제에 활용됩니다.
- 예제를 통해 BFS의 구조와 흐름을 이해하고, 문제에 따라 적절히 그래프/배열 기반의 BFS를 선택할 수 있어야 합니다.
728x90
반응형