[알고리즘]너비 우선 탐색(BFS)
너비 우선 탐색 (Breadth-First Search, BFS)
/image-20241031001807630.png)
- 시작 정점을 큐에 넣고 방문 처리한다.
- 큐에서 정점을 꺼내어 해당 정점에 인접한 정점들을 모두 큐에 넣는다. (이미 방문한 정점은 제외)
- 큐가 비워질 때까지 2의 과정을 반복한다.
BFS의 특징
- 최단 경로 탐색 : BFS는 너비 우선이므로 그래프에서 두 정점 간의 최단 경로를 찾을 때 유용하다.
- 큐(Queue) 사용 : 방문할 정점의 순서를 큐로 관리한다.
- 그래프의 모든 노드 탐색 : 연결 된 모든 정점을 방문할 때 사용한다.
BFS 구현 방법 1 : 인접리스트 사용
먼저 그래프를 인접 리스트로 표현한 후, BFS 적용
BFS로 최단 경로 찾기
package Graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BFSExample {
// 인접 리스트로 표현된 그래프
private static List<List<Integer>> graph = new ArrayList<List<Integer>>();
private static boolean[] visited;
// BFS 메서드
public static void bfs(int startNode){
Queue<Integer> queue = new LinkedList<Integer>(); // BFS에서 사용할 큐
queue.add(startNode);
visited[startNode] = true;
while(!queue.isEmpty()){ // 큐가 빌 때까지 반복
int currentNode = queue.poll(); // 큐에서 하나의 노드를 디큐함.
System.out.println(currentNode + ""); // 방문한 노드 출력(확인)
//현재 노드와 연결 된 모든 인접 노드를 확인한다.
for(int neighbor : graph.get(currentNode)){
if(!visited[neighbor]){ // 아직 방문하지 않은 정점이라면
queue.offer(neighbor); // 큐에 삽입하고
visited[neighbor] = true; // 방문 처리한다.
}
}
}
}
public static void main(String[] args) {
int numberOfNodes = 5; // 노드 개수 ( 0 ~ 4 )
visited = new boolean[numberOfNodes]; // 노드 방문여부 저장
// 그래프 초기화
for(int i=0; i<numberOfNodes; i++){
graph.add(new ArrayList<>()); // 각 노드마다 빈 리스트 추가
}
// 그래프의 간선 정보 추가 (무방향 그래프)
graph.get(0).add(1); graph.get(0).add(2); // 노드 0 -> 노드 1, 2
graph.get(1).add(0); graph.get(1).add(3); // 노드 1 -> 노드 0, 3
graph.get(2).add(0); graph.get(2).add(3); // 노드 2 -> 노드 0, 3
graph.get(3).add(1); graph.get(3).add(2); graph.get(3).add(4); // 노드 3 -> 노드 1, 2, 4
graph.get(4).add(3); // 노드 4 -> 노드 3
// bfs 수행
bfs(0);
}
}
최단 경로 찾기 - 실제 응용
package Graph;
import java.util.*;
public class ShortestPathBFS {
private static List<List<Integer>> graph = new ArrayList<>();
private static int[] distances; // 최단 경로를 저장하는 배열
public static void bfs(int startNode){
Queue<Integer> queue = new LinkedList<>();
queue.add(startNode);
distances[startNode] = 0; // 시작점의 거리는 0
while(!queue.isEmpty()){
int currentNode = queue.poll(); // 디큐
for(int neighbor : graph.get(currentNode)){
if(distances[neighbor] == -1){ // 아직 방문하지 않은 노드
distances[neighbor] = distances[currentNode] + 1;
queue.offer(neighbor); // 인큐
}
}
}
}
public static void main(String[] args) {
int numberOfNodes = 6;
distances = new int[numberOfNodes];
Arrays.fill(distances, -1);
for(int i=0; i<numberOfNodes; 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(2).add(0); graph.get(2).add(3);
graph.get(3).add(1); graph.get(3).add(2); graph.get(3).add(4);
graph.get(4).add(3); graph.get(4).add(5);
graph.get(5).add(4);
// bfs 실행
bfs(0);
// 각 노드로부터 최단 거리 출력
for (int i=0; i<numberOfNodes; i++){
System.out.println("Node "+i+" = "+distances[i]);
}
}
}
2D미로문제
- 미로는 2차원 배열로 주어지며, 시작 지점에서 출발하여 출구까지 도달하는 최단 경로를 구하는 것이 목표 최단 경로 = 너비우선탐색
문제 2D 미로에서 (0,0)위치에 있는 사람이 출구인 (n-1 ,m-1) 위치로 이동하려고 합니다. 이동할 수 있는 방향은 상,하,좌,우 4가지 입니다. 이동할 수 있는 칸은 1로 표시되고 이동할 수 없는 벽은 0으로 표시됩니다. 사람이 출구까지 이동할 수 있는 최단 경로의 길이를 구하세요
📍 1 ≤ N , M ≤ 100
📍 시작 지점 (0,0)에서 이동할 수 있는 칸은 1칸이며, 출구도 마찬가지로 이동할 수 있는 칸은 1칸입니다.
📍 dx, dy
📍 x축 이동 → 행 이동 ( 움직임은으로는 상하로 움직여야함)
📍 y축 이동 → 열 이동 ( 움직임으로는 좌우로 움직여야함)
cf) 아래의 코드에서 미로의 갈래가 여러 갈래인 건 고려할 필요가 없음. Queue의 특성상 각각의 경로를 다 찾으면서 마지막 distance에 각각의 경로가 증가한 값을 넣게 되고 최종적으로 목적지 (n,m)에 도달하는 점이 있으면 그 점에서 바로 return 하기 때문. 빙 돌아오는 다른 경로의 경우 distance값만 증가하고 결국 (n,m) 에 먼저 도달하지 못하기 때문에 고려XXX !!!!
package Graph;
import java.util.LinkedList;
import java.util.Queue;
public class MazeSolver {
// 방향을 나타내는 배열 (상,하,좌,우)
private static final int[] dx = {-1, 1, 0, 0}; // x축 이동
private static final int[] dy = {0, 0, -1, 1}; // y축 이동
// bfs 메서드 : 미로의 최단경로 찾기
public static int bfs(int[][] maze, int n, int m){
// 방문 여부를 저장하는 배열
boolean[][] visited = new boolean[n][m];
// bfs 탐색을 위한 큐 : {x, y, 현재까지 이동한 거리}
Queue<int[]> queue = new LinkedList<>();
// 시작점 (0,0)에서 탐색 시작
queue.offer(new int[]{0, 0, 1});
visited[0][0] = true; // 시작 지점 방문 처리
while(!queue.isEmpty()){
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int distance = current[2];
//출구에 도착하면 최단 경로 반환
if (x== n-1 && y== m-1){
return distance;
}
//상,하,좌,우 네방향으로 탐색
for(int i=0; i<4; i++){
int nx = x+dx[i];
int ny = y+dy[i];
//미로 범위를 벗어나지 않고, 이동할수 있는 칸이며, 방문하지 않았다면
if(nx >= 0 && ny >=0 && nx <n && ny < m && maze[nx][ny]==1 && !visited[nx][ny]){
queue.offer(new int[]{nx, ny, distance+1});
visited[nx][ny] = true; // 방문처리
}
}
}
// 출구에 도착하지 못하면 -1 반환
return -1;
}
public static void main(String[] args) {
// N x M 크기의 미로 입력
int[][] maze = {
{1, 0, 1, 1, 1},
{1, 0, 1, 0, 1},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 1},
{1, 1, 1, 1, 1}
};
int n = maze.length; // 미로의 세로 길이
int m = maze[0].length; // 미로의 가로 길이
// BFS 실행 및 결과 출력
int result = bfs(maze, n, m);
if (result != -1) {
System.out.println("최단 경로의 길이: " + result);
} else {
System.out.println("출구까지의 경로가 없습니다.");
}
}
}
이 외에 활용할 수 있는 문제 유형
섬의 개수 세기
0과 1 로 이루어진 2D 배열이 주어질 때, 1이 연속적으로 연결된 섬의 개수를 세는 문제.
섬은 상하좌우로만 연결 되어 있다.
🔍 Hint : 섬의 각 위치를 BFS로 탐색하여 방문한 위치를표시하고, 새로운 섬을 발견할 때마다 카운트를 증가시킨다.
바이러스 전파
2D 격자판이 주어질 때, 특정 위치에서 바이러스가 퍼지는 과정을 시뮬레이션하고
특정 시간이 지난 후에 감염 된 셀의 개수를 묻는 문제
🔍 Hint : BFS를 통해 감염된 셀에서 인접한 셀로 바이러스를 퍼뜨리며 시간 제한을 두고 진행한다.
미로탐색
주어진 미로에서 시작점에서 출발하여 목표지점까지 도달하는 최단 경로를 찾는 문제. 🔍 Hint : BFS를 사용하여 최단 경로를 탐색하고, 각 위치에서의 거리를 기록한다.
가장 먼 노드 찾기
주어진 그래프에서 가장 먼 노드를 찾는 문제.
노드와 간선이 주어질 때, 시작 노드에서 가장 먼 노드까지의 거리와 그 노드의 개수를 구합니다.
🔍Hint : BFS로 모든 노드를 탐색하여 각 노드까지의 거리를 기록하고, 가장 먼 거리를 찾아 수를 센다.
가장 짧은 경로
가중치가 있는 그래프에서 두 노드 간의 최단 경로를 찾는 문제
BFS와 dijkstra 알고리즘을 조합하여 해결
🔍 Hint : 가중치를 고려한 BFS를 통해 각 노드까지의 최단거리를 계산한다.
숨바꼭질
주어진 위치에서 시작하여 다른 위치로 이동하는 과정에서 숨바꼭질을 하는 문제 여러 가지 이동 방법이 주어지고, 몇 번의 이동으로 도착할 수 있는지를 묻는 문제
🔍 Hint : BFS로 모든 가능한 위치를 탐색하여 각 위치에서의 최소 이동 횟수를 계산한다.
퍼즐문제
숫자가 적힌 타일이 주어지고, 특정 규칙에 따라 타일을 이동시켜 목표 상태로 만드는 문제.
예를들어 3x3 퍼즐에서 공백을 이용하여 타일을 이동시키는 문제
🔍 Hint : BFS를 활용하여 가능한 모든 상태를 탐색하고, 목표 상태에 도달하는 최단 경로를 찾는다.
Leave a comment