자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : Tree 말단 노드까지의 가장 짧은 경로 (DFS)

 

 

https://hyejin.tistory.com/1260

자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 송아지 찾기 1 (BFS : Breadth-Firs

-> 이전 문제 풀이 

 

 

9. Tree 말단 노드까지의 가장 짧은 경로 (DFS) 

 

설명

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중

가장 짧은 길이를 구하는 프로그램을 작성하세요.

각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.

 

 

 

출력 

가장 짧은 길이는 3번 노느까지의 길이인 1이다.

 

 

문제 풀이  1

public class ShortestLengthToEndNode2
{
   Node root;
   
   public int DFS(int L, Node root)
   {
      if (root.lt == null && root.rt == null) { // 말단 node이라면 ?
         return L;
      }else
      {
         return Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt)); // 자식 node가 하나만 있으면 에러난다.
      }
   }
   public static void main(String[] args)
   {
      ShortestLengthToEndNode2 tree = new ShortestLengthToEndNode2();
      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);
      
      int result = tree.DFS(0, tree.root);
      System.out.println(result);
   }
}

👾 : 노드 문제가 계속 나오고 있기 때문에 class Node 만드는 코드는 생략했다. (이전 문제 풀이에서도 볼 수 있음) 

그리고 노드의 짧은 거리구하기 ~ 뭐 이런식의 문제는 DFS보다 BFS로 문제를 푸는 것이 더 낫다고 한다. 왜냐하면 DFS로 풀 경우 부모 노드의 자식 노드가 한쪽만 있거나 하면 에러가 발생하기 때문이다. 

 

아무튼.. 지금은 배우는 중이기 때문에 DFS로도 푸는 방법에 대해서도 배울 것이다. 

먼저 그림과 동일하게 트리를 만들어주고, DFS 로 문제를 푸는데 이때 root node와 레벨 (간선 길이)를 넘겨준다. 

 

 

public int DFS(int L, Node root)
{
   if (root.lt == null && root.rt == null) { // 말단 node이라면 ?
      return L;
   }else
   {
      return Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt)); // 자식 node가 하나만 있으면 에러난다.
   }
}

 

그리고 DFS 에서 root 의 lt와 rt가 null 이면 말단 노드라는 것이기 때문에 그대로 L 값을 넘겨준다. 

말단 노드가 아니라면 재귀 함수로 L +1 해서 lt와 rt 값을 각각 넘겨주고, 리턴 받은 L 값 중 Math.min 값을 구해서 리턴해주면 된다. 

 

 

 

말로 설명해보자면 DFS(1) 은 말단 노드가 아니었기 때문에 DFS(길이 1, 노드 2) 와 DFS(길이 2, 노드 3)을 호출할 것이다. 

 

먼저 스택에 쌓인 DFS(길이 1, 노드 2)도 역시 말단 노드가 아니기 때문에 DFS(길이 2, 노드 4), DFS(길이 2, 노드 5) 을 호출한다. 

이제 DFS(길이 2, 노드 4)와 DFS(길이 2, 노드 5)는 말단 노드 이기 때문에 L 인 2를 각각 리턴하고 DFS(길이 1, 노드 2)로 돌아오는데, 여기서 Math.min을 하기 때문에 노드 4와 노드 5의 길이 중 작은 값은 2이다. 

 

그리고 다음 스택에 쌓였던 DFS(길이 1, 노드 3)에서는 말단 노드였기 때문에 그대로 L 값 1을 리턴하고, 이제 DFS(길이 0, 노드 1)로 돌아간다. 

그럼 DFS(길이 0, 노드 1) 로 돌아오는데 이제 Math.min(node(2), node(3)) 에 대한 길이 중 최소 값은 1이었기 때문에 그대로 1을 리턴해주면 된다.