[코딩인터뷰완전분석] 트리와 그래프 2

<노드 사이의 경로>

방향 그래프가 주어졌을 때, 두 노드 사이에 경로가 존재하는가

---

내가 짠 코드

package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class pathExists {

	public static void main(String[] args) {
		// 방향 그래프
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for(int i = 0 ; i < 7; i++) {
			graph.add(new ArrayList<>());
		}
		graph.get(1).add(0);
		graph.get(1).add(5);
		graph.get(2).add(3);
		graph.get(2).add(4);
		graph.get(4).add(5);
		graph.get(5).add(2);
		graph.get(6).add(3);
		graph.get(6).add(4);
		boolean[] ans = path_Exists(5, 3, graph);
		for(int i = 0; i < 7; i++) {
			System.out.println(ans[i]);
		}
	}

	public static boolean[] path_Exists(int a, int b, ArrayList<ArrayList<Integer>> graph) {
		int n = graph.size();
		boolean[] visit = new boolean[n];
		for (int i = 0; i < n; i++) {
			visit[i] = false;
		}
		Queue<Integer> queue = new LinkedList<>();
		queue.add(a);
		visit[a] = true;
		while (!queue.isEmpty()) {
			int pop = queue.poll();
			ArrayList<Integer> temp = graph.get(pop);
			for (int i = 0; i < temp.size(); i++) {
				if (visit[temp.get(i)]) {
					continue;
				}
				queue.add(temp.get(i));
				visit[temp.get(i)] = true;
			}
		}
		return visit;
	}

}

---

결과                                       

그래프	결과

---

해답

그래프 탐색 기법인 DFS와 BFS를 사용해서 풀 수 있다.

두 노드 가운데 하나를 고른 뒤 해당 노드가 다른 노드에 도달할 수 있는지 확인하면 된다.

(나랑 똑같음!)

---

<최소 트리>

오름차순으로 정렬된 배열이 주어질 때, 높이가 최소가 되는 이진 탐색 트리를 만들어라.

---

내가 짠 코드

package tree;

import java.util.Arrays;

public class mintree {

	public static void main(String[] args) {
		int n = 9;
		int[] number = new int[n];
		for (int i = 0; i < n; i++) {
			number[i] = i;
		}
		myNode root = bst(number);
		printNode(root);
	}

	public static void printNode(myNode root) {
		if (root == null) {
			return;
		}
		String answer = "value : " + root.value;
		if(root.left != null) {
			answer += " left : " + root.left.value;
		}
		if(root.right != null) {
			answer += " right : " + root.right.value;
		}
		System.out.println(answer);
		printNode(root.left);
		printNode(root.right);
	}

	public static myNode bst(int[] number) {
		int len = number.length;
		if(len == 0) {
			return null;
		}
		if (len == 1) {
			return new myNode(number[0]);
		}
		int mid = len / 2;
		myNode left = bst(Arrays.copyOfRange(number, 0, mid));
		myNode right = bst(Arrays.copyOfRange(number, mid+1, number.length));
		return new myNode(number[mid], left, right);
	}

}

---

결과

BST

---

해답

최소 높이 트리로 만들기 위해서는 왼쪽 서브 트리와 오른쪽 서브 트리의 깊이가 같아야 한다. 따라서 root 값은 배열의 중앙값이어야 한다.

1. 배열의 중앙값을 트리에 삽입한다.
2. 왼쪽 하위 트리에 왼쪽 절반 배열 원소들을 삽입한다.
3. 오른쪽 하위 트리에 오른쪽 절반 배열 원소들을 삽입한다.
4. 재귀 호출을 실행한다.

비슷하게 푼거 같다.

---

<깊이의 리스트>

이진 트리가 주어졌을 때, 같은 깊이에 있는 노드들로 이루어진 연결 리스트를 만들어라.

---

내가 짠 코드

package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class treedepth {

	public static void main(String[] args) {
		myNode root = new myNode(0);
		myNode temp = new myNode(2, new myNode(4), new myNode(5));
		myNode temp1 = new myNode(1, temp, new myNode(3));
		temp = new myNode(8, new myNode(9), null);
		myNode temp2 = new myNode(6, new myNode(7), temp);
		root.left = temp1;
		root.right = temp2;

		ArrayList<ArrayList<myNode>> depth = bfs(root);
		for (int i = 0; i < depth.size(); i++) {
			ArrayList<myNode> al = depth.get(i);
			System.out.print("depth " + i + " : ");
			for(int j = 0; j < al.size(); j++) {
				System.out.print(al.get(j).value + " ");
			}
			System.out.println("");
		}

	}

	public static ArrayList<ArrayList<myNode>> bfs(myNode root) {
		ArrayList<ArrayList<myNode>> depth = new ArrayList<>();
		Queue<Tuple> queue = new LinkedList<>();
		int prev = -1;
		queue.add(new Tuple(0, root));
		while (!queue.isEmpty()) {
			Tuple tuple = queue.poll();
			if (prev != tuple.depth) {
				depth.add(new ArrayList<myNode>());
				prev++;
			}
			depth.get(prev).add(tuple.node);
			if (tuple.node.left != null) {
				queue.add(new Tuple(tuple.depth + 1, tuple.node.left));
			}
			if (tuple.node.right != null) {
				queue.add(new Tuple(tuple.depth + 1, tuple.node.right));
			}

		}
		return depth;
	}

}

class Tuple {
	int depth;
	myNode node;

	public Tuple(int d, myNode n) {
		this.depth = d;
		this.node = n;
	}
}

---

결과

트리	결과

---

해답

1. pre order 알고리즘을 살짝 변형하여 푼다.
2. BFS를 사용하여 푼다. -> 내가 푼 방법

---