섹션 7 Recursive, Tree, Graph - 10. Tree 말단 노드까지의 가장 짧은 경로

📌 문제 설명

주어진 이진트리에서 루트 노드(1번)부터 시작해
가장 가까운 말단 노드(leaf node) 까지 가는 최단 경로의 길이를 구하는 프로그램을 작성한다.

경로의 길이는 "이동한 간선(edge)의 개수"로 계산한다.

---

📝 입력 & 출력

입력

• 트리는 코드에서 직접 생성한다.

출력

• 루트 노드부터 가장 가까운 말단 노드까지 이동한 간선의 수를 출력한다.

---

🔹 예제 입력 & 출력

예제 입력 (트리 구조)

      1
    /   \
   2     3
  / \
 4   5

 

예제  출력

1

• 루트(1) → 오른쪽 자식(3)
• 1번 간선만 타면 말단 노드(3)에 도달

---

💡 해결 방법

• 가장 짧은 경로를 구해야 하므로 BFS(넓이우선탐색) 를 사용한다.
• BFS는 먼저 들어간 노드를 먼저 탐색하기 때문에, 말단 노드를 처음 발견했을 때가 가장 가까운 거리다.
• 레벨(Level) 개념을 이용해 이동한 간선 수를 계산한다.

---

💻 코드 구현 (Java)

전체 코드

package partRecursiveTreeGraph;

import java.util.*;

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

public class Problem9 {
	Node root;

	public int BFS(Node node) {
		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 0;
	}

	public static void main(String[] args) {
		Problem9 tree = new Problem9();
		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));
	}
}

---

📖 코드 설명

1️⃣ 큐(Queue) 초기화 및 시작 노드 삽입

Queue<Node> Q = new LinkedList<>();
Q.offer(root);
int L = 0;

• BFS 탐색을 위한 큐를 초기화하고 루트 노드를 삽입
• L은 현재 이동한 간선 수 (레벨)

---

2️⃣ BFS 탐색: 현재 레벨의 모든 노드 탐색

while (!Q.isEmpty()) {
	int len = Q.size();
	for (int i = 0; i < len; i++) {
		Node current = Q.poll();
		...
	}
	L++;
}

• 현재 큐에 있는 노드 수(len)만큼 꺼내며 탐색
• 같은 레벨에 있는 노드들을 모두 방문

---

3️⃣ 말단 노드(leaf node) 발견

if (current.lt == null && current.rt == null) return L;

• 꺼낸 노드가 왼쪽, 오른쪽 모두 자식이 없다면 → 말단 노드
• 이때까지 이동한 간선 수 L을 리턴하고 탐색 종료
• BFS 특성상 가장 먼저 찾은 말단 노드가 가장 짧은 거리다.

---

4️⃣ 자식 노드 큐에 삽입

if (current.lt != null) Q.offer(current.lt);
if (current.rt != null) Q.offer(current.rt);

• 왼쪽 자식이 있으면 큐에 추가
• 오른쪽 자식이 있으면 큐에 추가

---

⏳ 시간 복잡도 분석

• 모든 노드를 최대 한 번씩 방문 → O(N)
• 각 노드당 삽입/삭제 O(1) 작업
• 최종 시간 복잡도: O(N)

(N = 트리의 노드 개수)

---

🧠 핵심 정리

• 최단 거리는 DFS가 아니라 BFS로 구해야 한다.
• BFS를 하면서 가장 먼저 발견한 말단 노드가 최단 거리이다.
• 시간 복잡도는 O(N)으로 효율적이다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런