Java構文とアルゴリズム(BFS)


BFSとは?


最短距離を探すアルゴリズム
  • Queueによる階層ナビゲーション
  • 進行方法


    建造
  • ノード
  • キューを作成し、最初のノード
  • に入れる
  • while(!queue.isEmpty)はキューを行います.
  • forゲートで、残りのキューでノードに関連するノードキューを検索します.
  • キューからデータを取り出します.
  • は次に、キューに接続されたノードをキューに入れる.
  • forゲートが終了するとレベルが増加します.
  • 結果
    LEVEL 0 : 1
    LEVEL 1 : 2 -> 3
    LEVEL 2:4->5->6->7が回転し、接続がなくなりましたので、キューを終了します.
  • コード#コード#

    package inflearn.section7_bfs;
    
    import java.util.*;
    
    class Node {
        Node lt,rt;
        int data;
    
    
        Node(int value) {
            data=value;
            lt=rt=null;
        }
    
    }
    
    public class Main1 {
    
        Node root;
    
        public void bfs(Node root) {
            Queue<Node>queue=new LinkedList<>();
            // 값을 넣는다
            queue.add(root);
    
            int level=0;
    
            while (!queue.isEmpty()) {
                System.out.print(level+" : ");
                // 큐에서 한개 뽑는다.
    //            Node node=queue.poll();
                // 뽑은거 출력
                int size=queue.size();
                for (int i=0;i<size;i++) { // 여기서 주의! 큐에 들어가면서 큐 사이즈가 변하기 때문에 미리 큐 사이즈를 변수(size)에 저장한다.
    //                System.out.println("queue_size"+queue.size());
                    Node node=queue.poll();
                    System.out.print(node.data+" ");
    
                    // 왼쪽 오른쪽 넣기
                    if (node.lt!=null)  queue.add(node.lt);
                    if (node.rt!=null) queue.add(node.rt);
                }
                System.out.println();
                level++;
            }
    
        }
    
        public static void main(String[] args) {
            Main1 main=new Main1();
    
            // Node 생성
            main.root=new Node(1);
            main.root.lt=new Node(2);
            main.root.rt=new Node(3);
            main.root.lt.lt=new Node(4);
            main.root.lt.rt=new Node(5);
    
            main.root.rt.lt=new Node(6);
            main.root.rt.rt=new Node(7);
    
            // 이거 넣을때 주위, main.root를 넣어야 함
            main.bfs(main.root);
        }
    }

    に質問子牛をさがす



    解決策


  • 、文
  • forゲート、キュー周り接続(+1、-1、+5)
  • 級増加
  • 該当する数字が見つかった後、戻りゲートから退避してレベルを出力します.
  • package inflearn.section7_bfs;
    // 송아지 찾기 문제 BFS - 레벨 별 탐색
    
    
    import java.util.*;
    
    public class Main2 {
    
        // 전역변수
        static int n;
        static int m;
        int arr[]=new int[10001];
        int dx[]={-1,1,5};
        
        public int solution(int n) {
    
            Queue<Integer> queue=new LinkedList<>();
            int level=0;
            queue.add(n);
            // 처음 방문 -> 1로 처리 (방문 처리)
            arr[n]=1;
    
            while (!queue.isEmpty()) {
    
                int size=queue.size();
                for (int i=0;i<size;i++) {
    
                    int k=queue.poll();
    //                arr[k]=1; // 처음 갑
    
                    if (k==m) {
                        return level;
                    }
                    else {
                        for (int j=0;j<dx.length;j++) {
                            int nx=k+dx[j];
                            // 큐에 넣기
                            if (nx>=1 && nx<=10000  && arr[nx]==0) { // 방문하지 않았으면
                                arr[nx]=1; // 넣고 방문 처리
                                queue.add(nx);
                            }
                        }
                    }
                }
                level++;
            }
    
    
            int answer=0;
            return answer;
    
        }
    
        public static void main(String[] args) {
            Main2 main=new Main2();
            Scanner scan=new Scanner(System.in);
            n=scan.nextInt();
            m=scan.nextInt();
            System.out.println(main.solution(n));
    
        }
    }

    ツリー末端ノードへの最短パス



    コード#コード#

    package inflearn.section7_bfs;
    import java.util.*;
    class Node4 {
        Node4 lt;
        Node4 rt;
        int val=0;
    
        Node4(int val) {
            lt=rt=null;
            this.val=val;
        }
    }
    
    
    public class Main4 {
        Node4 node4;
    
        public int bfs(int l,Node4 node4) {
            Queue<Node4> queue=new LinkedList<>();
            queue.add(node4);
    
            while(!queue.isEmpty()) {
                int size=queue.size();
                for (int i=0;i<size;i++) {
                    Node4 node=queue.poll();
    
                    // 말단 노드
                    if (node.lt==null && node.rt==null) {
                        return l;
                    }
                    queue.add(node4.lt);
                    queue.add(node4.rt);
                }
                l++;
            }
    
            return 1;
        }
    
    
        public static void main(String[] args) {
            Main4 main4 =new Main4();
            main4.node4=new Node4(1);
            main4.node4.lt=new Node4(2);
            main4.node4.rt=new Node4(3);
    
            main4.node4.lt.lt=new Node4(4);
            main4.node4.lt.rt=new Node4(5);
    
            int l=0;
            System.out.println(main4.bfs(l,main4.node4));
    
        }
    
    }