10. 말단 노드까지 최소 간선 BFS

1. 문제

 

최소 간선의 길이를 BFS로 풀기

 

 

2 - 1. 나의 풀이

그냥 기본적인 BFS에 Node.lt ==null &&Node.rt == null 이면 해당 계층을 반환하면된다.

 

주의할 점은

for문에서 i < q.size()를 쓰면 안되고

int len = q.size()를 한다음 i < len으로 적어야한다.

for문을 돌면서 q의 사이즈가 계속 늘어나기 때문이다.

 

 

2 - 2. 나의 코드

package BFS_DFS;
import java.util.*;

class Node {
    int data;
    Node lt, rt;

    Node(int value) {
        this.data = value;
    }
}

public class bfs10 {
    static Node root;

    public static int BFS(int L,Node root) {
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int len = q.size();
            for (int i = 0; i < len; i++) {
                Node tmp = q.poll();
                if(tmp.lt ==null && tmp.rt ==null) return L ;
                if(tmp.lt != null) q.offer(tmp.lt);
                if(tmp.rt != null) q.offer(tmp.rt);
                }
            L++;
        }

        return 0;
    }

    public static void main(String[] args) {
        root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
        
        System.out.println(BFS(0,root));
    }
}

 

3. 강의

나와 같다.

 

 

4. 얻어갈 점

for문이 돌면서 큐의 크기가 변하므로 int len = q.size()로 for문 돌기전 큐의 크기를 저장해두는것이 중요하다.