DFS&BFS 활용 - Tree 말단 노드까지 가장 짧은 경로 구하기

오늘은 지난 포스팅인 DFS & BFS 기초에 이어서 알고리즘을 활용하여 Tree 말단 노드까지의 가장 짧은 경로를 구하는 간단한 문제를 풀어 볼 예정입니다😄

 

DFS & BFS 활용

 

개요

사실 최단 경로를 구하는 문제는 대게 BFS(넓이 우선 탐색)를 이용하여 문제를 풀지만, DFS로도 풀 수 있는 문제가 왕왕 있기 때문에 2가지 문제 풀이법 모두 진행해보려 합니다.

 

트리 구조

 

문제는 위 그림처럼 1번 노드에서 시작해 가장 말단 노드까지 가는 최단 경로를 구하는 문제입니다. 여기서 말단 노드는 하위 노드가 없는 노드를 뜻하며 그림에서는 4, 5, 3에 해당하겠네요!

 

가장 짧은 간선을 구하기 때문에 한 개의 간선만 필요한 3번 노드가 말단 노드로 지정되고, 정답은 간선의 개수이기 때문에 1이 되겠습니다😊

 

이전 포스팅과 마찬가지로 Node 클래스는 전역으로 사용하기 때문에 따로 클래스로 선언하였습니다. 코드가 이해 안되시는 분들은 이전 포스팅을 클릭하셔서 확인해주시면 될 것 같아요. 

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

 

그럼 이제 DFS와 BFS 코드를 구현해 볼까요?

 

DFS📘

public class DFSTree {
    Node root;
     public int DFSTree(int L, Node root) {
        if(root.lt == null && root.rt == null) return L;
        else return Math.min(DFSTree(L+1, root.lt), DFSTree(L+1, root.rt));
    }
    
    public static void main(String[] args) {
        DFSTree tree = new DFSTree();
        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.DFSTree(0, tree.root));
    }
}

먼저 개요에 있는 그림과 같이 트리를 구성해주었어요. 그리고 DFSTree 함수를 호출하게 돼요. 인자값인 L은 레벨을 뜻하고 맨 처음 즉, 트리의 맨 꼭대기는 0 레벨로 지칭하였어요.

 

인자값 root 즉 1의 lt값은 2, rt값은 3으로 null이 아니기 때문에 else문을 타게 되고, DFSTree() 함수를 재귀적으로 호출하게 됩니다. 여기서 DFSTree(0+1, 2)로 값이 들어가게 되겠네요. 그러면 rt값을 호출하는 DFSTree() 함수는 당연히 스택에 쌓인 채로 왼쪽 먼저 진행하게 됩니다.

 

이제는 L이 1이 되었고, 다시 한번 똑같이 root 2의 함수가 돌아가게 됩니다. 2의 lt는 4, rt는 5이기 때문에 다시 한번 else문을 타게 됩니다. 여기서도 rt값인 5는 스택에 쌓이겠죠?

 

이제는 L이 2인 상태로 root 4의 함수가 돌아갑니다. root 4는 말단 노드이기 때문에 lt,rt 값이 존재하지 않아서 L값 2를 return 하게 됩니다.

 

그다음은 스택에 쌓여있던 root 5의 함수가 돌아가게 되고, root 4와 마찬가지로 말단 노드이기 때문에 L값 2를 리턴합니다. Math.min() 함수는 2개의 값 중에 작은 값을 리턴하는데 지금은 값이 동일하기 때문에 2가 return 됩니다.

 

마지막으로 맨 처음 스택에 쌓였던 root 1의 rt값 root 3의 함수가 돌아갑니다. root 3의 lt, rt 값이 없기 때문에 L값 1을 리턴합니다. 이제 마지막으로 Math.min(왼쪽 2, 오른쪽 1) 함수가 실행되어 최종적으로 1을 return 하게 됩니다.

 

📌 스택 그림을 그리면서 따라가보시면 이해하시기 편하실 것 같아요😄

 

BFS📙

그렇다면 BFS 동작방식은 어떻게 될까요?

public class BFSTree {
    Node root;
    public int BFS(Node root) {
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0;
        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i = 0; i < len; ++i) {
                Node current = Q.poll();
                if(current.lt == null && current.rt == null) return L;
                if(current.lt != null) Q.offer(current.lt);
                if(current.rt != null) Q.offer(current.rt);
            }
            L++;
        }
        return L;
    }
    
    public static void main(String[] args) {
        BFSTree tree = new BFSTree();
        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.BFS(tree.root));
    }
}

Tree는 동일하게 구성됩니다. 이 후에 처음으로 BFS() 함수를 호출시키고 인자값으로 root 1이 넘어가게 됩니다. BFS() 함수에서는 넘어온 값 1을 Queue에 넣고 while문이 Queue가 비어있을 때까지 돌아가게 됩니다.

 

while문 안에서 Queue의 사이즈만큼 반복문이 돌고 Queue에서 값을 꺼내면서 꺼내진 해당 root의 lt값과 rt값의 유무를 체크하고 있을시에는 Queue에 추가하게 됩니다.

 

여기서는 1의 lt값 2와 rt값 3이 Queue에 추가 되겠네요!

 

이후에 레벨은 한 단계 상승합니다. 그리고 다시 Queue가 비어있지 않기 때문에(현재 Queue = 2,3) 반복문이 돌아가게 됩니다. Queue에서 값을 꺼낸 root 2는 lt값 4와 rt값 5가 있기 때문에 Queue에 넣어줍니다(현재 Queue = 3,4,5)

 

그다음 반복문 인자는 Queue에 root 3입니다. 하지만 root 3은 lt값과 rt값이 없기 때문에 반복문이 종료되고 return 값은 현재 L값인 1이 됩니다.

 

---

👨‍👩‍👦‍👦 오픈채팅방 운영

취업을 준비하는 예비 개발자분들을 위한 질문&답변할 수 있는 공간을 만들었습니다. 취업과 이직을 하기 위해서 어떤 걸 중점적으로 준비해야 하는지부터 포트폴리오&이력서 작성법 등 다양한 질문들을 받고 답변을 드립니다. 참여하셔서 다양한 정보 얻고 가시면 좋을 것 같네요😁

 

참여코드 : 456456

https://open.kakao.com/o/gVHZP8dg

비전공 개발자 취업 준비방(질문&답변)

 

---

👨‍💻 전자책 출간

아울러 제가  🌟비전공자에서 2년만에 보안 전문 중견기업으로 이직 한 방법들을 정리한 전자책을 출간 하게 되었습니다. 어떤 걸 공부해야 하는지, 이직을 위해서 무엇을 준비해야 하는지, 제가 받았던 기술 면접 리스트 등 다양한 목차로 구성되어 있습니다. 또한, 구매 시 1:1 채팅을 이용하여 포트폴리오 첨삭을 도와드리고 있습니다. 🐕전자책으로 얻은 모든 수익은 유기견 센터 '팅*벨 입양센터'에 후원될 예정입니다. 관심 있으신 분들은 아래 링크를 참고해주세요😁

https://kmong.com/gig/480954

비전공개발자 2년만에 중견기업 들어간 방법 | 14000원부터 시작 가능한 총 평점 0점의 전자책, 취

---

 

마치며

최단 경로 구하는 문제는 코딩 테스트의 기본 문제이기 때문에 탐색 알고리즘의 기본인 DFS와 BFS를 활용한 2가지 해결법 모두 숙지하고 있으면 좋을 것 같아요. 혹여나 이해가 안 되셨다면 기본적인 Statck, Queue에 대한 이해가 먼저 필요하기 때문에 이전 포스팅들을 참고하시면 됩니다! 다음 포스팅에서 뵐게요😊