[BFS] 10. 말단노드까지의 가장 짧은 경로

<<풀이>>
 
-나의 풀이-
 
원래 최단 거리는 BFS로 푸는 것이 정석이다.
 
그렇기 이번에는 BFS를 활용해서 풀었다. while 문과 Queue를 활용해서 풀었다.
 
그렇게 해서 문제를 맞췄는데 !!! 
 
내가 실수 한 것이 있었다.
 
그건 바로 말단 노드의 오개념이었다.
 
나는 말단 노드를 하나만 null이면 끊겼다고 착각했다.
 
하지만 하나만 null이라도 null 아닌 쪽으로 말단 노드는 더 아래로 갈 수 있는 것이다 ㅋㅋ 

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node lt ,rt;

    Node(int val) {
        data = val;
        lt = rt = null;
    }
}

class Main {
    Node root;
    
    private int BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0;
        while(!Q.isEmpty()) {
            int size = Q.size();
            for (int i = 0; i < size; i++) {
                Node n = Q.poll();
                if (n.lt == null || n.rt == null) return L;
                else {
                    Q.offer(n.lt);
                    Q.offer(n.rt);

                }
            }
            L++;
        }
        return 0;
    }

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

 
 
그래서 수정한 것이 강사님 코드이다.
 
-강사님 풀이-
 
or => and 로 바꿔준 형태이다.
 
정답이라서 자칫 넘어가 다음에도 생길 문제를 오늘 잡아서 다행이라고 생각한다 ㅎㅎ

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node lt ,rt;

    Node(int val) {
        data = val;
        lt = rt = null;
    }
}

class Main {
    Node root;

    private int BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0;
        while(!Q.isEmpty()) {
            int size = Q.size();
            for (int i = 0; i < size; i++) {
                Node n = Q.poll();
                if (n.lt == null && n.rt == null) return L;
                else {
                  if(n.lt != null)  Q.offer(n.lt);
                  if(n.rt != null)  Q.offer(n.rt);

                }
            }
            L++;
        }
        return 0;
    }


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