4. 트리와 그래프 문제 해법

노드 사이의 경로

방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성하라.

그래프 탐색 기법, 즉 너비 우선 탐색이나 깊이 우선 탐색을 사용해서 풀 수 있다. 두 노드 가운데 하나를 고른 뒤 탐색 도중 다른 노드가 발견되는지 검사하면 된다. 중복되는 일을 피하기 위해 방문한 노드는 이미 방문했음을 표시해 두어야 한다.

public class Answer {
	public static void main(String[] args) {
		
	}
	
	public static class Graph {
		public Node[] getNodes() {
			return null;
		}
	}

	public static class Node {
		State state;
		public Node[] getAdjacent() {
			return null;
		}
	}
    
	enum State { Unvisited, Visited, Visiting; }

	boolean search(Graph g, Node start, Node end) {
		if(start == end) return true;
		
		// Queue처럼 작동
		LinkedList<Node> q = new LinkedList<Node>();
		
		// graph에 있는 모든 node들의 상태를 Unvisited 상태로 초기화한다.
		for(Node u : g.getNodes()) {
			u.state = State.Unvisited;
		}
		
		// start 지점의 state를 Visiting으로 바꾼다.
		start.state = State.Visiting;
		q.add(start);
		Node u;
		
		
		while(!q.isEmpty()) {
			u = q.removeFirst(); //dequeue()와 같다.
			if(u != null) {
				
				// 인접한 모든 node를 반복시킨다.
				for(Node v : u.getAdjacent()) {
					
					// 방문되어 있지 않은 state가 존재한다면, 그것이 end node인지 파악한다.
					// end이면 true를 return, 그렇지 않다면 상태를 Visiting으로 바꾸고,
					// queue에 추가시킨다.
					if(v.state == State.Unvisited) {
						if(v == end) {
							return true;
						} else {
							v.state = State.Visiting;
							q.add(v);
						}
					}
				}
				
				// for문이 끝나면 해당 node를 Visited 상태로 바꾼다.
				u.state = State.Visited;
			}
		}
		
		// 모두 돌았음에도 불구하고, return true를 만나지 못했다면 그래프 상으로 만나지 못하므로
		// false를 return 한다.
		return false;
	}
}

 

최소 트리

오름차순으로 정렬된 배열이 있다. 이 배열 안에 들어 있는 원소는 정수이며 중복된 값이 없다고 했을 때 높이가 최소가 되는 이진 탐색 트리를 만드는 알고리즘을 작성하라.

최소 높이 트리를 생성하기 위한 조건은 다음과 같다.

- 왼쪽 하위 트리의 노드의 개수와 오른쪽 하위 트리의 노드 개수를 가능하면 같게 맞춘다.
- 루트 노드가 배열의 중앙에 오도록 한다.
=> 트리 원소 가운데 절반은 루트보다 작고, 나머지 절반은 루트보다 커야 한다.

즉, 배열에서 각 구획의 중간 원소가 루트가 될 것이며, 루트의 왼쪽 절반은 왼쪽 하위 트리, 오른쪽 절반은 오른쪽 하위 트리가 될 것이다. 이 문제를 풀기 위해 재귀적 방식으로 root.insertNode(int v)메서드를 제작하게 되면, 결국에는 최소 높이 트리를 만들수는 있지만, 원소를 삽입할 때마다 트리를 순회해야 하므로 또 다른 방법의 고안이 필요로 하다.

바로 createMinimalBST라는 이름으로 책에 저자는 메서드를 제작했는데, 이는 부가적으로 발생하는 트리 순회 비용을 절감할 수 있으니 확이해보길 바란다. 알고리즘은 다음과 같다고 한다.

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

class TreeNode {
	int data;
	TreeNode left;
	TreeNode right;
	
	TreeNode() {}
	TreeNode(int data) {
		this.data = data;
	}
	
	// 배열이 들어왔을 때에 그 배열을 가지고 처음과 끝 정보를 넘겨
	// 중간부분을 찾기 위한 메소드
	TreeNode createMinimalBST(int array[]) {
		return createMinimalBST(array, 0, array.length - 1);
	}
	
	// 배열로부터 start 지점과 end 지점이 입력으로 들어왔을 때
	// mid를 계산하여 좌 우로 나눈다.
	// 각 나누어진 부분은 다시 하나의 배열이 되어 재귀적 호출이 이루어지고,
	// 처음 if문에 의해 걸러질 때까지 재귀적 호출이 연속적으로 이루어진다.
	TreeNode createMinimalBST(int arr[], int start, int end) {
		if(end < start) {
			return null;
		}
		int mid = (start + end) / 2;
		TreeNode n = new TreeNode(arr[mid]);
		n.left = createMinimalBST(arr, start, mid - 1);
		n.right = createMinimalBST(arr, mid + 1, end);
		return n;
	}
}