[JAVA] 알고리즘 문제풀이 기초 - DFS, BFS

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

• DFS 버전 기초 구현
  

import java.util.*;

class Node {
    int data;
    Node lt, rt;
    public Node (int value){
        data = value;
        lt=rt=null;
    }
}

public class Main {

    Node root;
    public int DFS(int L, Node root){
        if(root.lt==null && root.rt==null) {
            return L;
        }

        int r1 = DFS(L+1, root.lt);
        int r2 = DFS(L+1, root.rt);

        return Math.min(r1,r2);
    }

    public static void main(String[] args) {
        Main tree = new Main();
        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);
        System.out.println(tree.DFS(0,tree.root));
    }
}

• 정리
  1. 왼쪽 오른쪽 null일때만 레벨값을 반환하도록 하고 null이 아니면 계속 재귀
     
  2. 둘중 작은값(더 짧은경로)를 최종값으로 사용
     
     
     
• BFS 버전 기초 구현. BFS가 정석 접근 풀이임
  
  

import java.util.*;

class Node {
    int data;
    Node lt, rt;
    public Node (int value){
        data = value;
        lt=rt=null;
    }
}

public class Main {

    Node root;
    public int BFS(int L, Node root){

        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        int size = q.size();

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

    public static void main(String[] args) {
        Main tree = new Main();
        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);
        tree.root.lt.lt.lt=new Node(8);
        tree.root.lt.lt.rt=new Node(9);

        System.out.println(tree.BFS(0,tree.root));
    }
}

• 정리
  1. 기존의 큐를 사용해서 BFS 도는것은 동일
     
  2. 하위 노드가 없을때는 바로 리턴