Algorithm - Shortest Distance ( DFS, BFS )

• 2023-12-22
• DFS 와 BFS 로 최단거리를 구하는 알고리즘을 공부한 내용입니다.

1. DFS를 활용한 최단거리 구하기

• DFS 로도 최단거리를 구할 수는 있다.
• 그러나 말단 노드를 제외한 모든 노드의 자식이 무조건 2개가 있어야한다.
• 그렇지 않으면 오류가 발생한다.
• 코드에서 자식 노드 2개를 반드시 검사하기 때문이다. ( 없으면 2개가 다 없는지로 검사한다. )

  public int DFS ( int level, Node root ) {
   if ( root.lt == null && root.rt == null ) return level;
   else return Math.min( DFS(level+1, root.lt), DFS(level+1, root.rt) );
  }
  

2. BFS를 활용한 최단거리 구하기

• 최단 거리는 이렇게 BFS로 구하는것이 제일 좋다.
• lt, rt 둘 다 없으면 말단 노드이므로, 가장 처음 등장한 말단노드 레벨이 최단거리이다.

  public int BFS ( Node root ) {
   Queue<Node> Q = new LinnkedList<>( );
   Q.offer(root);
   int level = 0;
   while ( ! Q.isEmpty( ) ) {
      int len = Q.size( );
      for ( int i=0; i<len; i++ ) {
         Node curr = Q.poll( );
         if ( curr.lt == null && curr.rt == null ) return level; // 가장 빨리 찾은 말단 노드
         if ( curr.lt != null ) Q.offer(curr.lt);
         if ( curr.rt != null ) Q.offer(curr.rt);
      }
      level ++ ;
   }
   return level;
  }