노드 최단거리 (DFS)
설명
말단 노드까지 가장 짧은 경로를 구하세요.
코드
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));
}
}
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는 스택 프레임의 구조를 이해하며 항상 풀어내자!
Author And Source
이 문제에 관하여(노드 최단거리 (DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ililil9482/노드-최단거리-DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)