DFS, 우선 순위 큐

1. DFS

  1) DFS란

    - 깊이 우선 탐색

    - 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 방문하는 순회방법

    - 스택을 사용

 

---

 

2. 이진트리 순회

  1) 순회 방법

    - 전위 순회 : VLR

    - 중위 순회 : LVR

    - 후위 순회 : LRV

	public void dfsByPreorder() {
		if (isEmpty()) {
			System.out.println("==========preorder========");
			dfsByPreorder(1);
			System.out.println();
		}
	}

	private void dfsByPreorder(int current) {

		System.out.println(nodes[current] + "\t");

		// 왼쪽 자식 노드
		if (current * 2 <= lastIndex)
			dfsByPreorder(current * 2);
		// 오른쪽 자식 노드
		if (current * 2 + 1 <= lastIndex)
			dfsByPreorder(current * 2 + 1);
	}

	public void dfsByInorder() {
		if (isEmpty()) {
			System.out.println("==========inorder========");
			dfsByPreorder(1);
			System.out.println();
		}
	}

	private void dfsByInorder(int current) {

		// 왼쪽 자식 노드
		if (current * 2 <= lastIndex)
			dfsByPreorder(current * 2);

		System.out.println(nodes[current] + "\t");

		// 오른쪽 자식 노드
		if (current * 2 + 1 <= lastIndex)
			dfsByPreorder(current * 2 + 1);
	}
	
	public void dfsByPostorder() {
		if (isEmpty()) {
			System.out.println("==========postorder========");
			dfsByPreorder(1);
			System.out.println();
		}
	}

	private void dfsByPostorder(int current) {

		// 왼쪽 자식 노드
		if (current * 2 <= lastIndex)
			dfsByPreorder(current * 2);

		// 오른쪽 자식 노드
		if (current * 2 + 1 <= lastIndex)
			dfsByPreorder(current * 2 + 1);
		
		System.out.println(nodes[current] + "\t");
	}

	@Override
	public String toString() {
		return "CompleteBinaryTree [nodes=" + Arrays.toString(nodes) + ", SIZE=" + SIZE + ", lastIndex=" + lastIndex
				+ "]";
	}

 

---

 

3. 힙

  1) 힙이란?

    - 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드가 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

    - 최대 힙 : 부모 노드의 키 값 >= 자식 노드의 키 값

    - 최소 힙 : 부모 노드의 키 값 <= 자식 노드의 키 값

 

---

 

4. 우선순위 큐

  1) 구현

import java.util.PriorityQueue;
 
public class Example {
    public static void main(String[] args) {
 
        // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        // 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
		// PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
 
        pQ.offer(1);    // pQ에 원소 1 추가
        pQ.offer(6);    // pQ에 원소 6 추가
        pQ.offer(2);    // pQ에 원소 2 추가
        
        // pQ가 비어있면: true, 그렇지 않으면 : false
        while(!pQ.isEmpty()) {
            // pQ에 첫 번째 값을 반환하고 제거, 비어있다면 null 반환
            System.out.println("pQ.poll() = " + pQ.poll());
        }
 
    }
}

 

  2) 객체 우선순위 큐

import java.util.Comparator;
import java.util.PriorityQueue;
 
class Student {
    int mathScore; // 수학점수
    int engScore;  // 영어점수
 
    public Student(int mathScore, int engScore){
        this.mathScore = mathScore;
        this.engScore = engScore;
    }
}
// 클래스 객체의 우선순위를 위한 클래스
class StudentComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        if (o1.mathScore == o2.mathScore) {
            return o2.engScore - o1.engScore;
        } else {
            return o1.mathScore - o2.mathScore;
        }
    }
}
 
public class Example {
 
    public static void main(String[] args) {
 
        // 클래스 객체에 대한 우선순위 기준 제공
        PriorityQueue<Student> pQ = new PriorityQueue<>(1, new StudentComparator());
 
        pQ.offer(new Student(70, 50));  // 우선순위 큐에 클래스 객체를 추가
        pQ.offer(new Student(60, 50));  // 우선순위 큐에 클래스 객체를 추가
        pQ.offer(new Student(70, 40));  // 우선순위 큐에 클래스 객체를 추가
 
        while (!pQ.isEmpty()) {
            Student s = pQ.poll();
            System.out.printf("Student\'s MathScore and engScore: %d, %d \n", s.mathScore, s.engScore);
        }
    }
}