<Tree traverse>
java에서 binary tree는 간단히 node class로 구현이 된다.
그 후, traverse에는 2가지 방식이 있는데..
DFS: Depth First Search - 깊이 부터 서치하는 일반적인 방식.
이렇게 node로 구성된 BinaryTree 를 DFS로 traverse하는 방법에는 2가지가 있는데
1. recursive (좀 안좋은: 참고 )
출력은: printInOrder(node) {
if (node!=null) {
printInOrder(node.left);
System.out.println(node.value);
printInOrder(node.right);
}
2. loop 이용.. loop를 이용한 방법은 다음과 같다. myREF REF
주로 stack이용.
BFS: Breadth First Search - 같은 depth에 있는 형제들 먼저 출력. (아래코드 참조) -Queue이용.
q.add(root);
while (q.size() > 0) {
node = q.poll();
print ( node.value );
if (node.left != null) q.add( node.left);
if (node.right !=null) q.add (node. right);
}
<Direct Graph Traverse>
Dijkstra : Vertex(node)---edge---> w 로 갈 때 각 Edge마다 Weight가 있는 경우, 적합.
log(n^2)으로 vertex를 늘여가면서 가까운 Destination으로의 path를 찾아나간다.
핵심공식: distance[w] = min(distance[w], distance[u] + weight[u][w])
(아래 표 참조 1에서 출발:)
w S D(2) D(3) D(4) D(5)
1 S{1} 10 무한 30 100
2 S{1,2} 10 60 30 100
1에서 가까운 w를 하나씩 추가하면서 진행해 나가므로, 가까운 Vertex관리가 필요한데,
A. (Linked)adjacent List 로 관리하거나
B. priority Queue로 관리할 수 있다. (모든 Vertex에서 다해도 되지만, S 에 들어가는 거 위주로 해도 된다.)
BFS: tree에서 처럼 weight없이 탐색한다. 탐색방식은 Dijkstra와 근본적으로 같다.
<MST:min Spanning Tree> REF
Prim 알고리듬: O(n^2) => 보통 점만 주어질 땐, link가 많으므로 이럴때 적합.
- 노드 하나를 기준으로 그 외부와 연결되는 가장 min 값을 연결한다.
- 연결된 Set 과 그 외부 Set(외부를 전체 Set으로 보고) 또 가장 min 값을 연결한다.
(구현이 간단함)
내가 구현한 예제: disjointSet 이용.
int dist(int[] p1, int[] p2) {
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
class Node {
int id; //1~5
int dist;
int pid1;
int pid2;
public Node(int pid1, int pid2,int id, int dist) {
this.pid1 = pid1;
this.pid2 = pid2;
this.id = id;
this.dist = dist;
}
}
/** MAIN */
public int minCostConnectPoints(int[][] points) {
if (points.length <= 1 ) return 0;
//4point case: 3*2 = 6개? (n-1!)
int N = points.length;
//20개 중 작은값 4개를 뽑아서 더하면 될듯. (단 이미연결된거 방지 체크)
//int dists[] = new int[ N * (N-1)];
PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node n1, Node n2) {
return n1.dist - n2.dist;
}
}
);
//10개 노드: 4 + 3+ 2+ 1
int id = 0;
for (int i = 0; i < N-1; i++) {
for (int j = i+1; j < N; j++) {
Node node = new Node( i, j, id++, dist(points[i], points[j]));
pq.add(node);
}
}
System.out.println( "Total NODE: :" + id);
//필요 node는 (n-1)! -1 ///////////////////////
int k = N - 1;
int totDist = 0;
// HashSet<Integer> hs = new HashSet<>();
DjSet djSet = new DjSet(N);
while (pq.size() > 0) {
// while (k > 0) {
Node node = pq.poll();
System.out.println("node poll:" + k);
//TODO check.
if (!djSet.isConnected(node.pid1, node.pid2)) {
//add node.pid1, node.pid2
djSet.union(node.pid1, node.pid2);
totDist += node.dist;
k--;
}
//DjSet 도입이전 코드: 섬이 2개 생기면 이미 추가되어서 오류가 생김.
// if ( !hs.contains(node.pid1) || !hs.contains(node.pid2) ) {
// //System.out.println(node.dist + "," + node.pid1 + "," + node.pid2 + ",");
// hs.add(node.pid1);
// hs.add(node.pid2);
//
// totDist += node.dist;
// k--;
// }
}
return totDist;
}
구현에 DisjointSet(서로소 집합)과 union 이 필요할 것 같아서 링크 REF
/////////// DjSet: find, union, isConnected ////////////////////////////
class DjSet {
int[] parent;
int[] size;
public DjSet(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
//find parent //////////////
int find(int x) { //union하면서 아직 update안된 parent들 udpate하면서 find
if (parent[x] != x) {
parent[x] = find(parent[x]); // 경로 압축: 부모를 찾아서 업데이트하면서 재귀적으로 호출
}
return parent[x]; // 노드 x의 부모 반환
}
boolean isConnected(int x, int y) {
return find(x) == find(y);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (size[rootX] > size[rootY]) parent[rootY] = rootX;
else if (size[rootX] < size[rootY]) parent[rootX] = rootY;
else {
parent[rootY] = rootX;
size[rootX]++;
}
}
}
구현에 DisjointSet(서로소 집합)과 union 이 필요할 것 같아서 링크 REF
Kruskal 알고리듬: O(eloge) - e 가 적당하다면 이 알고리듬이 훨씬 낫다.
- 일단 min Edge 들을 연결한다. (단 cycle이 안생기는 방식으로 연결)
- 마지막엔 Set 과 Set 간 연결들이 필요.
<TSP: Travelling Salesman Problem>
모든 노드를 한번씩만 돌아서 다 돌때 최소 weight 찾는 문제로, 일반적으로 알고리듬이 없다.
즉 모든 경우의 수를 다 해봐야 한다.
====Tree BFS code (순서없이 BFS Breadth First Search )======
위에 5줄이면 충분함. detail을 포함한 세부구현은 아래 더보기 참조.
class Node{
int value;
Node left;
Node right;
public Node (){
left=right=null;
}
public Node (int v){
value = v;
}
}
class Test {
/* DFS */
public void printInOrder(Node node){ //이함수는 DFS recursive test용 임.
if (node != null){
printInOrder(node.left);
out(":" +node.value);
printInOrder(node.right);
}
}
/* simple class for Marking a New Line in the Queue
*/
class NewLine extends Node{
}
/* print same depth nodes at the same line
* @param binTree : root Node of binary Tree
*/
public void printBFSTree(Node binTree){
if (binTree == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add( binTree );
queue.add( new NewLine()); //depth seperator
while (queue.size() > 0){
Node node = queue.poll();
if ( node instanceof NewLine) { //(Depth changed)
System.out.println(); //print new Line
if (queue.size() > 0)
queue.add(node); //add NewLine for added sibling
}else { //(general Node)
//print Node's value
System.out.print(node.value + " ");
}
if (node.left != null) {
queue.add( node.left );
}
if (node.right != null) {
queue.add( node.right );
}
}
}
