BFS
BFS ?
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 시작 노드로부터 가까운 노드들부터 먼저 탐색하는 알고리즘이다.
- 무방향 그래프나 가중치가 동일한 그래프에서 최단 경로를 보장하지 때문에, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
- 그래프나 트리의 모든 정점을 특정 레벨 순서로 탐색할 때 적합하다 !
💡 BFS 핵심 개념 - 방문 여부 체크
- DFS와 동일하게 방문 여부를 체크해야 한다.
💡 DFS 핵심 개념 - 그래프 구현 방법에 따라 달라지는 시간 복잡도
노드의 수 = V, 간선의 수 = E
- 인접 리스트를 이용한 방법 - O(V + E)
- 모든 노드 방문 - O(V) → BFS는 모든 노드를 한 번씩 방문하기 때문에 O(V) 시간 복잡도가 요구된다.
- 간선 탐색 - O(E) → 각 노드에서 해당 노드와 연결된 모든 간선을 하나씩 탐색하기 때문에 O(E) 시간 복잡도가 요구된다. → 따라서, 간선 개수가 적은 희소 그래프를 탐색해야 하는 경우에 효율적이다 !
<aside> 💡
인접 리스트란 ?
- 각 노드마다 해당 노드에 연결된 간선 정보를 2차원 배열로 저장하는 방식이다.
( ex: 노드 1: [2, 5] → 노드 1에 노드 2, 5가 연결되어 있다. )
</aside>
- 인접 행렬를 이용한 방법 - O(V^2)
- 모든 노드 방문 - O(V) → 인접 리스트 구현 방식과 동일하게 모든 노드를 한 번씩 방문하기 때문에 O(V) 시간 복잡도가 요구된다.
- 간선 탐색 - O(V) → 인접 행렬에선 노드간 연결 여부를 확인하기 위해선 모든 노드 쌍을 확인해야 하기 떄문에 O(V) 시간 복잡도가 요구된다.
<aside> 💡
인접 행렬이란 ?
- 노드 간의 연결 관계를 2차원 배열로 저장하는 방식이다.
( ex: matrix[u][v] = 1 → 노드 u, v를 연결하고 있는 가중치값이 1인 간선 정보 )
</aside>
💡 BFS 핵심 개념 - Queue
- 방문하지 않은 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 Queue를 사용한다.
- 따라서, BFS는 재귀적으로 동작하지 않는다. → 하지만, Queue에 정점들을 저장해야 하기 때문에 많은 메모리를 사용할 수 있다. 특히, 정점의 개수가 많거나 그래프가 넓게 퍼져 있는 경우 메모리 부담이 커질 수 있다 !
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
queue.offer(neighbor);
visited[neighbor] = true;
}
}
}
}
문제: 미로 탐색 (백준 2178)
문제 링크
알고리즘 [접근 방법]
- BFS를 이용하여 목적지 노드까지 이동할 수 있는 최단 경로를 구하면 된다.
해결 코드
- 거리 배열 추가: distance 배열을 사용하여 각 위치에 도달할 때의 최소 칸 수를 저장한다. → distance[x][y]는 (x, y) 위치까지 도달하는 데 필요한 최소 칸 수를 나타낸다.
- 거리 계산: BFS 탐색 시, 현재 위치에서 다음 위치로 이동할 때 distance[nextX][nextY] = distance[currentPoint.x][currentPoint.y] + 1로 최소 칸 수를 업데이트한다.
- 방향 배열 사용: dx와 dy 배열을 사용하여 상하좌우로 이동할 수 있는 위치를 쉽게 계산한다.
- 그래프 입력: graph를 인접 리스트로 구현하여 입력받았으며, 이동할 수 없는 칸(0)을 제외한다.
import java.util.*;
public class Main {
static int ROW, COL;
static List<List<Point>> graph;
static boolean[][] visited;
static int[][] distance;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ROW = sc.nextInt();
COL = sc.nextInt();
sc.nextLine(); // 개행 문자 처리
graph = new ArrayList<>();
visited = new boolean[ROW][COL];
distance = new int[ROW][COL];
// 그래프 초기화
for (int i = 0; i < ROW; i++) {
graph.add(new ArrayList<>());
}
// 그래프 입력
for (int i = 0; i < ROW; i++) {
String line = sc.nextLine();
for (int j = 0; j < COL; j++) {
if (line.charAt(j) == '1') { // 이동 가능한 칸만 추가
graph.get(i).add(new Point(i, j));
}
distance[i][j] = Integer.MAX_VALUE; // 초기 거리를 무한대로 설정
}
}
bfs(0, 0); // (0, 0) 위치에서 시작
// 도착 위치까지의 최소 칸 수 출력
System.out.println(distance[ROW - 1][COL - 1]);
}
static void bfs(int x, int y) {
Queue<Point> queue = new LinkedList<>();
queue.offer(new Point(x, y));
visited[x][y] = true;
distance[x][y] = 1; // 시작 칸은 1로 설정
while (!queue.isEmpty()) {
Point currentPoint = queue.poll();
for (int i = 0; i < 4; i++) {
int nextX = currentPoint.x + dx[i];
int nextY = currentPoint.y + dy[i];
// 범위를 벗어나는 경우
if (nextX < 0 || nextX >= ROW || nextY < 0 || nextY >= COL) {
continue;
}
// 이동할 수 없는 칸이거나 이미 방문한 경우
if (visited[nextX][nextY] || graph.get(nextX).isEmpty()) {
continue;
}
queue.offer(new Point(nextX, nextY));
visited[nextX][nextY] = true;
distance[nextX][nextY] = distance[currentPoint.x][currentPoint.y] + 1;
}
}
}
}
정리
- 어떤 노드에서 특정 노드까지의 최단 거리를 구하는 문제이면 BFS를 떠올리자 !
https://thin-azimuth-2a9.notion.site/GDG-BFS-13df4ee21c0080a0a5bac0d53f171945?pvs=4
