자바 문법 및 알고리즘 (BFS)

BFS란?

• 최단 거리를 찾는 알고리즘
• Queue를 사용하며 Level별 탐색을 함
  

진행방법

• 노드를 만든다
• 큐를 만들어서 첫번째 노드를 넣는다
• while (!queue.isEmpty)로 큐를 진행한다.
• for문으로 남아 있는 큐를 돌면서 Node와 연결된 노드를 큐를 찾는다.
• 큐에서 데이터 1개를 빼낸다. (여기선 첫번째로 1이 빠지게 됨)
• 그리고 큐에 연결된 노드를 넣는다.
• 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);
    }
}

문제 1. 송아지 찾기

해결방법

• while 문
• for문으로 큐를 돌고 연결한다 (+1, -1, +5)
• Level을 증가
• 해당 숫자를 찾으면 return문으로 빠져 나와 레벨을 출력한다.

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));

    }
}

Tree 말단 노드까지의 가장 짧은 경로

코드

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));

    }

}