BFS(Breadth First Search)

루트 노드에서 시작해 인접한 노드를 전부 탐색하는 방법
레벨 1에서 레벨 2로 가기위해서는 레벨 1에서의 모든 경우의 수를 파악하고 2단계로 넘어감

인접한 노드를 전부 탐색한다의 의미

처음의 위치에서 시작해서 최소의 거리(level)를 먼저 방문한다라는 것으로 문제에서,
1) 최소의 칸수를 지나야할 때
2) 최단거리
3) 한칸에 1초씩 지날 때 최소의 시간
이렇게 최단경로를 파악하기 위해 BFS를 사용하게 된다.
BFS는 지나가는 경로의 순서를 보장하지 못한다
경로의 순서를 저장하고 싶을 때는 dfs를 사용할 것..

BFS 탐색에서 큐를 사용하는 이유는?

Queue는 FIFO구조로 First in First Out이다.
즉 가까운 거리를 먼저 다 탐색해서 처리한 후 그 다음 레벨들을 Queue에 저장해 대기시킨다.
<위의 그림은 레벨1의 데이터가 queue에서 뽑혀서 처리되면서 이후 레벨들을 queue에 넣은 작업>

BFS 시간복잡도

인접행렬 구현 : O(N^2)
인접리스트 구현 : O(N+E) (N: 각 정점 한번씩 방문 E: 간선에 대해 1번씩 검사)

BFS코드 예시

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BFS {

    static class Node{
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int dr[] ={1,-1,0,0};
    static int dc[]={0,0,1,-1};
    static int arr[][];
    public static void bfs()
    {
        //visited 배열은 당시의 상태를 저장하는 배열(방문한 상태인지, 안한 상태인지)
        boolean visited[][]=new boolean[arr.length][arr.length];
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(5,5));
        visited[5][5]=true;
        arr[5][5]=1;
        while(!q.isEmpty())
        {
            int level = q.size();
            //for문을 통해 level이 나누어짐..
            for(int s=0;s<level;s++) {
                Node n = q.poll();
                for (int k = 0; k < 4; k++) {
                    int nr = n.r + dr[k];
                    int nc = n.c + dc[k];
                    //if문을 통해 예외처리
                    if (nr < 0 || nr >= arr.length || nc < 0 || nc >= arr[0].length || visited[nr][nc]) continue;
                    //bfs조건 구현부분
                    q.add(new Node(nr, nc));
                    arr[nr][nc] = 1;
                    visited[nr][nc] = true;
                }
            }
            print();
        }
    }
    public static void print()
    {
        for(int i=0;i<arr.length;i++)
        {
            System.out.println(Arrays.toString(arr[i]));
        }
        System.out.println("===========END===========");
    }
    public static void main(String[] args) {
        arr=new int[10][10];
        bfs();

    }
}