[JAVA][알고리즘] BFS

💡BFS

BFS는 너비 우선 탐색으로, 루트 노드에서 탐색을 시작하여 같은 레벨에 있는 노드를 모두 탐색한 다음

하위 레벨로 내려가 또 모두 탐색을 진행하다가, 더 이상 탐색할 노드가 없을 때 탐색을 멈추는 방식으로 동작한다.

 

큐를 이용하여 구현한다.

 

💡 BFS 코드구현

import java.util.*;

class Node{
    int data;
    Node lt,rt;
    public Node(int val){
        data=val;
        lt=rt=null;
    }
}
public class Solution {
    Node root;
    public void BFS(Node root) {
        Queue<Node> Q=new LinkedList<>();
        Q.offer(root);
        int L=0;
        while(!Q.isEmpty()){
            int len=Q.size();
            System.out.print(L+" : ");
            for(int i=0; i<len; i++){
                Node cur=Q.poll();
                System.out.print(cur.data+" ");
                if(cur.lt!=null) Q.offer(cur.lt);
                if(cur.rt!=null) Q.offer(cur.rt);
            }
            L++;
            System.out.println();
        }
    }
    public static void main(String[] args) {
        Solution tree=new Solution();
        tree.root=new Node(1);
        tree.root.lt=new Node(2);
        tree.root.rt=new Node(3);
        tree.root.lt.lt=new Node(4);
        tree.root.lt.rt=new Node(5);
        tree.root.rt.lt=new Node(6);
        tree.root.rt.rt=new Node(7);
    }
}

 

 

 

 

 

💡 BFS 송아지 문제

 

 

import java.util.*;

public class Solution {
    int[] dis={1,-1,5};
    int[] ch; // 이미 있는 값인지 check 할 배열
    Queue<Integer> Q=new LinkedList<>(); // 전역 Q 선언

    public int BFS(int s, int e){ // s = 출발점 / e = 도착지점
        ch=new int[10001];
        ch[s]=1;
        Q.offer(s);
        int L=0; // root node level = 0
        while(!Q.isEmpty()){
            int len=Q.size(); // 레벨의 길이
            for(int i=0; i<len; i++){
                int x=Q.poll();
                if(x==e) return L;
                for(int j=0; j<3; j++){
                    int nx=x+dis[j]; // nx : 자식 node
                    if(nx>0 && nx<=10000 && ch[nx]==0){ // ch[nx]==0이면 방문 X
                        ch[nx]=1; // 방문했다고 check
                        Q.offer(nx);
                    }
                }
            }
            L++; // level 증가
        }
        return 0;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner kb=new Scanner(System.in);
        int s=kb.nextInt();
        int e=kb.nextInt();
        System.out.println(T.BFS(s,e));
    }
}

 

 

 

💡DFS, BFS를 활용하면 좋은 상황

1. 그래프의 모든 정점을 방문하는 것이 주요한 문제 : DFS, BFS 모두 무방

 

2. 경로의 특징을 저장해둬야 하는 문제 : 각 정점에 숫자가 있고 a 부터 b 까지 가는 경로를 구하는데 같은 숫자가 있으면 안된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 하는 경우는 DFS를 사용해야 한다. 

BFS는 경로의 특징을 저장하지 못한다.

 

3. 최단거리를 구하는 문제 : BFS가 유리하다. DFS의 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, BFS의 경우 먼저 찾아지는 해답이 곧 최단거리이기 때문이다.