[PS] 인프런 강의 - Tree 5. Tree 말단 노드까지의 가장 짧은 경로

 

문제

아래 그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를구하는 프로그램을 작성하세요.
각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다.

 

가장 짧은 길이는 3번 노느까지의 길이인 1이다.

 

풀이

위 그림과 달리 예를 들어 노드 3이 왼쪽 자식만 가지고 있다고 할 때는 DFS로 풀기에 제약이 있다. (왼쪽, 오른쪽 자식으로 뻗는다는 가정이 있기 때문에)

 

DFS 코드 (자식 하나만 가지는 노드가 있으면 에러남)

import java.util.Scanner;

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

public class Main {
	
	//레벨 탐색
	public static int DFS(int L, Node root) {
		if(root.lt == null && root.rt == null) return L;
		else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt));
	}
	

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        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(5);
        
        System.out.print(DFS(0, root));
    }
}

 

그것 때문이 아니더라도 에지 개수는 즉 레벨 개수이므로 BFS로 푸는게 맞다.

 

BFS(넓이우선탐색)로 말단 노드, 즉 왼쪽 & 오른쪽 자식이 없는 노드를 가장 먼저 발견했을 때의 레벨을 반환하면된다.

 

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

public class Main {
	
	//레벨 탐색
	public static 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 cur = Q.poll();
				
				if(cur.lt == null && cur.rt == null) return L;

				if(cur.lt != null) Q.offer(cur.lt);
				if(cur.rt != null) Q.offer(cur.rt);
			}
			L++;
		}
		return L;
	}
	

	public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        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(5);
        
        System.out.print(BFS(root));
    }
}