[알고리즘][BFS] BFS 기본 개념

[알고리즘][BFS] BFS 기본 개념

• BFS (Breadth First Search) ; 너비 우선 탐색

- 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식

- 큐에 넣을 때 방문 check 해준다.

• 탐색 방법

• 코드 구현

* BFS의 구현은 Queue를 이용

- 인접행렬을 이용한 코드 구현

    int n = scan.nextInt(); //접점의 수
    int m = scan.nextInt(); //간선의 수
    int[][] array = new int[n][m];
    boolean[] check = new boolean[n];
    Queue<Integer> queue = new LinkedList<>(); // 큐
    
    public void BFS1() {    
        check[1] = true;
        queue.offer(1);
        while(!queue.isEmpty()) {
            int x = queue.peek();
            queue.poll();
            for(int i=0;i<=n;i++) {
                if(array[x][i]==1 && check[i]==false) { // x번 접점의 1인 i를 모두 검사 
                    check[i]=true;
                    queue.offer(i);
                }
            }
        }
    }

- 인접리스트를 이용한 코드 구현

    ArrayList<ArrayList<Integer>> a = new ArrayList<>(); //인접리스트
    boolean[] check = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
 
    public void BFS2() { 
        check[1] = true;    
        queue.offer(1);
        while(!queue.isEmpty()) {
            int x = queue.peek();
            queue.poll();
            
            for(int i=0;i<a.get(x).size();i++) {    // 접점 x 안에 들어있는 list 사이즈만큼 반복
                if(check[i]==false) {
                    check[i]=true;
                    queue.offer(i);
                }
            }
        }
    }