[알고리즘] BFS - 너비 우선 탐색 (JAVA)

 

 

BFS란

• 루트 노드 (혹은 시작 노드)에서 시작하여 인접한 노드를 먼저 방문하는 알고리즘입니다. 즉 DFS와 같이 깊이를 먼저 탐색하는 것이 아니라 자신 주변을 넓게 탐색하여 너비 우선 탐색이라고 불립니다.
• BFS로 최단경로를 찾을 수 있는 이유는 한 정점에서 연결되는 모든 길을 "한번씩" 탐색하기 때문입니다. 특정 노드와 연결된 노드 사이의 길이는 1이기 때문에 같은 방식으로 모든 노드 사이의 거리를 구할 수 있기 때문입니다. 하지만 가중치가 있는 그래프의 경우 BFS를 사용할 수 없습니다 ! 

출처: 나무위키

 

---

BFS의 특징 

• 그래프 탐색 시, 어떤 노드를 방문했는지 여부를 반드시 검사해야 합니다. 검사하지 않았을 경우, 무한루프에 빠질 수 있습니다. 
• BFS 알고리즘은 일반적으로 선입선출(FIFO)의 특징을 가지는 큐 자료구조를 사용합니다.
• 보통은 가중치가 없는 그래프에서 최단 경로를 찾거나, 임의의 경로를 찾고자 할 때 사용합니다

 

---

Queue 구현 시, LinkedList  ? or ArrayDeque ?

• ArrayDeque는 Queue의 서브 인터페이스인 Deque의 구현체, LinkedList는 List와 Quque의 구현체 ! 

- 연산 성능

• ArrayDeque과  LinkedList 모두 원소의 삽입/삭제 연산은 O(1)로 뛰어납니다. 하지만 원소를 조회하는 속도에서 차이가 나는데, LinkedList의 경우 O(n)의 시간복잡도를 가지지만 ArrayDeque의 경우엔 O(1)의 성능을 가집니다. 그 이유는 LinkedList에서는 순차접근만 가능하기 때문입니다. 

- 메모리  

• LinkedList의 경우에는 next, prev와 같은 참조자 또한 저장해줘야 하기 때문에 추가적인 메모리를 할당해야 합니다. 그렇기에 ArrayDeque보다 추가적인 공간이 더 필요할 수 밖에 없는 구조입니다. 

 

---

BFS 예시

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

소스코드

package Baekjoon.BFS;
import java.util.*;
import java.io.*;

class P2178 {
    static int[][] arr;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static int N,M;
    static boolean[][] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N][M];

        for (int i=0;i< N;i++) {
            String s = br.readLine();
            for (int j=0;j<M;j++) {
                arr[i][j] = s.charAt(j)- '0';
            }
        }

        visited = new boolean[N][M];
        visited[0][0] = true;
        BFS(0,0);
        sb.append(arr[N-1][M-1]);
        System.out.println(sb);

    }   
    
    public static void BFS(int x, int y) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node (x,y));

        while (!q.isEmpty()) {
            Node cur = q.poll();

            for (int i=0; i<4;i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M) { // 범위 안에 있으면서
                    if (!visited[nx][ny] && arr[nx][ny] != 0) { // 아직 방문 X, 0이 아닌경우
                        visited[nx][ny] = true;
                        arr[nx][ny] = arr[cur.x][cur.y] + 1;
                        q.add(new Node(nx,ny));
                    }
                }
            }
        }
    }
}

class Node {
    int x;
    int y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}