[Algorithm] - BFS(Breadth-First Search)
알고리즘 문제에서 자주 다뤄지는 BFS에 대해 알아보자.
BFS란?
BFS는 말 그대로 너비 우선 탐색으로 깊게 탐색하는 dfs와는 달리 인접한 노드부터 넓게 탐색하는 방법이다.
임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 말한다.
BFS 사용하는 경우: 두 노드 사이의 최단경로 or 임의의 경로를 찾고 싶을 때
ex) 어떤 지점 a에서 b까지 이동하는 거리를 그래프로 표현한 후 a와 b사이에 존재하는 경로를 찾는 경우
> DFS - 일단 한 경로를 선택하여 끝까지 가보고 막혔다면 다시 이전 분기점으로 돌아와 탐색
> BFS - 시작점과 가까운 곳부터 '차례대로' 살펴보며 탐색
BFS 특징
1️⃣ 재귀적으로 동작 x
2️⃣ 노드 방문 여부를 반드시 검사해야한다.
: 방문한 노드를 재방문할 경우 무한루프에 빠지게 될 위험이 있다.
3️⃣ 대부분 Queue를 사용해 구현
: FIFO의 특성을 이용
: 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다.
BFS 이해
📌 배열에서 BFS
배열에서 BFS는 다양한 문제로 많이 나온다.
예를 들어 (미로를 탈출하기 위한 최단 경로 구하기), (장애물을 피하며 시작위치에서 종료위치까지 가는 최단 경로 구하기)등이 있다.
아래와 같은 배열이 있다고 가정해보자.
S가 시작위치 E가 종료위치이다. S에서 장애물을 피하면서 E로 가는데 최단 경로를 구해보자.
(S: 시작점, E: 종료점, X: 장애물)
BFS는 시작위치와 인접한 위치부터 탐색한다고 했다.
1. S와 인접한 위치부터 탐색
우선 시작점인 S를 큐에 넣고 큐에서 S(0)을 제거하고 제거한 위치와 인접한 위치인 1과 2를 넣는다
큐 : 1(1), 2(1)
()의 수는 시작점으로부터 거리를 나타낸다.
2. 큐에서 1(1)을 제거한다.
큐에서 빼낸 거리에 +1을 해줘야하고 1과 인접한 3을 넣어준다.
큐: 2(1), 3(2)
3. 큐에서 2(1)을 제거 후 4 넣는다.
큐: 3(2), 4(2)
4. 큐에서 3(2)를 제거 후 5 넣는다.
큐: 4(2), 5(3)
5. 큐에서 4(2)를 제거 후 6 넣는다.
큐: 5(3), 6(3)
6. 큐에서 5(3)을 제거 후 7 넣는다.
큐: 6(3), 7(3)
7. 큐에서 6(3)을 제거하게되고, 인접한 곳이 E이므로 E(4)로 종료한다.
S에서 E까지의 최단 거리는 4라는 것을 확인할 수 있다.
위의 과정을 자바코드로 구현해보자.
시작위치에서부터 상하좌우로만 움직일 수 있으며, 장애물이 있는 X로는 이동할 수 없다.
예시)
5 5
SOOOX
OXXOX
OXXOX
OXXOX
EOOOX
전체 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static Queue<int[]> q= new LinkedList<>();
private static int [] dx = {1,0,-1,0};//x축 이동 값
private static int [] dy = {0,1,0,-1};//y축 이동 값
private static boolean [][] visited;//방문 여부 배열
private static int [][] arr;//전체 배열 저장
private static int R,C;
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st= new StringTokenizer(br.readLine());
R=Integer.parseInt(st.nextToken());
C=Integer.parseInt(st.nextToken());
arr=new int[R][C];
visited= new boolean[R][C];
for(int i=0; i<R; i++){
String inputRow = br.readLine();
for(int j=0;j<C;j++){
char inputCol = inputRow.charAt(j);
if(inputCol == 'S'){//시작점인 경우
q.add(new int[]{i, j, 0});//시작 위치부터 큐에 넣기
visited[i][j] = true; //시작위치 방문 완료 처리
}
arr[i][j] = inputRow.charAt(j);
}
}
BFS();
}
public static void BFS(){
while(!q.isEmpty()){
int [] cur = q.poll();//큐에서 하나 뽑아서 배열에 저장
for(int i=0;i<dx.length;i++){ //인접한 위치 탐색
int nextR = cur[0] + dx[i];
int nextC = cur[1] + dy[i];
int nextDist = cur[2] + 1;
if(nextR < 0 || nextR >= R || nextC <0 || nextC >=C || visited[nextR][nextC] || arr[nextR][nextC] == 'X'){
continue; //다음으로 탐색할 위치가 범위를 벗어난 곳이거나 이미 방문한 곳이라면 탐색하지 x
}
if(arr[nextR][nextC] == 'E'){//최종 목적지인 E에 도착한 경우
System.out.println(nextDist);//경로 출력
return;
}
q.add(new int[]{nextR,nextC,nextDist});//큐에 다음으로 탐색할 곳 넣기
visited[nextR][nextC] = true;// 큐에 넣은 곳 방문 체크
}
}
System.out.println(-1); //S에서 E로 이동하지 못하는 경우
}
}📌 그래프에서 BFS
그래프 구현방식으로는 두가지가 있다.
1. 인접행렬
2. 인접리스트
✏️ 구현과정
아래와 같은 그래프에서 1번에서 출발하여 6번까지 가려고 하는 경우 최단 경로를 구해보자.
1. 시작점인 1을 큐에 넣는다.
1(0)
2. 큐에서 1을 빼고 1과 인접한 2와 3을 넣는다.
2(1) 3(1)
3. 큐에서 2를 빼고 2와 인접한 4를 넣는다.
4(2) 3(1)
4. 큐에서 3을 빼고 인접한 곳이 5와 6이다. 6은 목적지이므로 6(1+1)해서 최단 거리는 2인 것을 확인할 수 있다.
위의 과정을 자바코드로 구현해보자.
그래프는 6개의 정점과 8개의 간선으로 이루어져있고. 그 아래에는 8줄에 걸쳐 간선 정보가 주어진다.
예시)
6
8
1 2
1 3
2 3
2 4
3 5
3 6
4 6
5 6
✏️ 인접행렬로 구현
인접행렬로 구현하기 위해서는 인접행렬 배열을 만들어줘야 한다.
🔎 구조
- 인접행렬 배열(boolean [][] edge)
- 방문여부 배열(boolean[] visited)
- 큐(Queue<Integer> q)
- 거리 정보 저장(int [] dist)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
private static int n,e;
private static boolean [][] edge;
private static boolean [] visited;
private static int [] dist;
private static Queue<Integer> q=new LinkedList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
e = Integer.parseInt(br.readLine());
edge = new boolean[n+1][n+1]; // 간선 정보 저장
while (e-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
edge[a][b] = true;
edge[b][a] = true; // 양방향 간선이므로 반대방향도 넣어줘야 함.
}
BFS();
}
public static void BFS(){
visited = new boolean[n+1]; // 방문체크
dist = new int[n+1]; // 거리정보
Arrays.fill(dist, -1);
q.add(1);
visited[1] = true;
dist[1] = 0;
while (!q.isEmpty()) {
int cur = q.poll();
for (int i = 1; i <= n; i++) {
if (!edge[cur][i] || visited[i]) {
continue; // 간선정보가 없는 위치거나 이미 방문했다면 무시
}
int next = i;
q.add(next); // 다음 간선 번호를 큐에 넣음
visited[next] = true; // 방문 완료
dist[next] = dist[cur] + 1; // 거리 정보
if (i == n) {
break; // 목적지에 도달했다면 반복문 종료
}
}
}
System.out.println(dist[n]);// 방문한적 없다면 -1이 출력
}
}
시간복잡도 : O(N^2)
✏️ 인접리스트로 구현
인접행렬에서 간선(edge)을 저장하는 배열만 바꾸면된다.
🔎 구조
- 인접행렬 배열(ArrayList<Integer> [] edge)
- 방문여부 배열(boolean[] visited)
- 큐(Queue<Integer> q)
- 거리 정보 저장(int [] dist)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static int n,e;
private static ArrayList<Integer>[] edge;
private static boolean [] visited;
private static int [] dist;
private static Queue<Integer> q=new LinkedList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
e = Integer.parseInt(br.readLine());
edge = new ArrayList[n+1]; // 간선 정보 저장
for (int i = 1; i <= n; i++) {
edge[i] = new ArrayList<>();
}
while (e-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
edge[a].add(b);
edge[b].add(a); // 양방향 간선이므로 반대방향도 넣어줘야 함.
}
BFS();
}
public static void BFS(){
visited = new boolean[n+1]; // 방문체크
dist = new int[n+1]; // 거리정보
Arrays.fill(dist, -1);
q.add(1);
visited[1] = true;
dist[1] = 0;
while (!q.isEmpty()) {
int cur = q.poll();
for (int next : edge[cur]) {
if (visited[next]) {
continue; // 이미 방문했다면 무시
}
q.add(next); // 다음 간선 번호를 큐에 넣음
visited[next] = true; // 방문 완료
dist[next] = dist[cur] + 1; // 거리 정보
if (next == n) {
break; // 목적지에 도달했다면 반복문 종료
}
}
}
System.out.println(dist[n]);// 방문한적 없다면 -1이 출력
}
}
시간복잡도: O(N + E)