Recursive, Tree, Graph 4 - Tree 말단노드까지 가장 짧은 경로 DFS, BFS

학습자료 : https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84#

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

 

 

문제 :

이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램 작성하시오.

사실 이런 문제는 DFS보다 BFS로 푸는 것이 좋다.

왜냐하면 3번 노드의 자식이 한 쪽만 있을 경우 DFS의 경우엔 에러가 발생하기 때문이다.

단지 연습 차원에서 DFS로 코드를 작성해보자

 

소스코드 (DFS) :

import java.util.*;
class Node {
	int data;
	Node lt, rt;
	public Node(int value) {
		data = value;
		lt = rt = null;
	}
}
class Main {
	Node root;
	public int DFS(int level, Node root) {
		// 말단 노드
		if (root.lt == null & root.lt == null) return level;
		else {
			return Math.min(DFS(level+1, root.lt), DFS(level+1, root.rt));
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		// Scanner sc = new Scanner(System.in);
		T.root = new Node(1);
		T.root.lt = new Node(2);
		T.root.rt = new Node(3);
		T.root.lt.lt = new Node(4);
		T.root.lt.rt = new Node(5);
		System.out.println(T.DFS(0, T.root));
	}
}

 

 

앞서 말했듯이 이런 문제는 BFS로 푸는 것이 좋다.

 

소스코드 (BFS) :

import java.util.*;
class Node {
	int data;
	Node lt, rt;
	public Node(int value) {
		data = value;
		lt = rt = null;
	}
}
class Main {
	Node root;
	public int BFS(Node root) {
		Queue<Node> Q = new LinkedList<>();
		Q.offer(root);
		int level = 0;
		while (!Q.isEmpty()) {
			int len = Q.size();
			// 해당 레벨에 있는 노드 모두 빼내기
			for(int i=0; i<len; i++) {
				Node curNode = Q.poll();
				if (curNode.lt == null && curNode.rt == null) return level;
				if (curNode.lt != null) Q.offer(curNode.lt);
				if (curNode.rt != null) Q.offer(curNode.rt);
			}
			level++;
		}
		return 0;
	}

	public static void main(String[] args) {
		Main T = new Main();
		// Scanner sc = new Scanner(System.in);
		T.root = new Node(1);
		T.root.lt = new Node(2);
		T.root.rt = new Node(3);
		T.root.lt.lt = new Node(4);
		T.root.lt.rt = new Node(5);
		System.out.println(T.BFS(T.root));
	}
}