설명

말단 노드까지 가장 짧은 경로를 구하세요.

코드

public class ShortNodeDFS {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(4);
        System.out.println(dfs(0, root));
    }

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

가장 짧은 경로를 구하는건 BFS가 최선이지만 DFS로도 구하는 방법을 알아봤다. 하지만 이 문제에서 노드는 무조건 위 코드와 같이 말단의 노드는 자식 노드를 단 1개라도 가져서는 안된다는 조건이 있다.

이 코드에서 가장 잘 이해해야하는 부분은 dfs 내부 로직 자체인데

if(root.lt==null && root.rt==null) return level;

이 부분은 위에서 말한 조건대로 말단 노드의 경우 자식이 없으므로 말단 노드인지 판단 후 말단 노드라면 해당 레벨을 반환하는 조건이다.

그리고 그 밑에 코드인

return Math.min(dfs(level+1, root.lt), dfs(level+1, root.rt));

해당 코드가 중요하다. 스택 프레임의 구조를 이해하고 있다면 쉽게 이해할 수 있을 것이다. Math.min()을 통해 해당 노드의 왼쪽 자식과 오른쪽 자식이 말단 노드인지 확인한 후 말단 노드라면 level 값이 반환되며 프레임을 하나씩 반환 받으며 최종 받은 최소값을 계산하는 것이다.

DFS는 스택 프레임의 구조를 이해하며 항상 풀어내자!