[탐색 알고리즘] 그래프, DFS, BFS

💡그래프란?

정점(node) 와 그 정점을 연결하는 간선( edge)로 이루어진 자료구조

그래프 탐색의 종류 2가지 : DFS, BFS

---

💡깊이 우선 탐색(DFS)

📌 개념

• 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대깊이 까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색하는 알고리즘

• 완전 탐색 기법 중 하나

• 완전 탐색 기법

  • 특징
    • 재귀함수로 구현
    • 스택 자료구조 이용

📌 특징

• 모든 노드를 방문하고자 하는 경우 이 방법을 사용
• 너비 우선 탐색 보다 더 간결함
• 검색 속도는 너비 우선 탐색에 비해 느리다

📌 DFS 템플릿 코드

static Set<String> visited = new HashSet<>();

static void dfs(Map<String, List<String>> graph, String current) {
    // *---------------------------------------*
		// 그래프를 방문하며 처리해야할 일을 여기서 한다
		// (예시)
	  // if (current == value) {
		//     << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
		//     return current;
		// }
    // *---------------------------------------*
    visited.add(current);
    for (String v : graph.get(current)) {
        if (!visited.contains(v)) {
            dfs(graph, v);
        }
    }
}

---

💡너비 우선 탐색(BFS)

### 📌 개념

• 완전 탐색 기법
• 시작 노드에서 인접한 노드를 먼저 탐색하고, 그 다음 인접한 노드를 탐색하는 알고리즘

📌 특징

• 완전 탐색 기법
• 큐 자료구조 이용
• 최단 경로를 찾을 때 유용

📌 BFS 템플릿 코드

public static void makeGraph() {
    graph.put(0, Arrays.asList(1, 3, 6));
    graph.put(1, Arrays.asList(0, 3));
    graph.put(2, Arrays.asList(3));
    graph.put(3, Arrays.asList(0, 1, 2, 7));
    graph.put(4, Arrays.asList(5));
    graph.put(5, Arrays.asList(4, 6, 7));
    graph.put(6, Arrays.asList(0, 5));
    graph.put(7, Arrays.asList(3, 5));
}

Set<String> bfs(Map<String, List<String>> graph, String start) {
    Set<String> visited = new HashSet<>();
    visited.add(start);
    Queue<String> queue = new ArrayDeque<>();
    queue.add(start);

    while (!queue.isEmpty()) {
        String current = queue.remove();
		    // *---------------------------------------*
				// 그래프를 방문하며 처리해야할 일을 여기서 한다
				// (예시)
			  // if (current == value) {
				//     << 현재 노드가 특정 값을 만족할 때 해야할 일 >>
				//     return current;
				// }
		    // *---------------------------------------*
        for (String v : graph.get(current)) {
            if (!visited.contains(v)) {
                visited.add(v);
                queue.add(v);
            }
        }
    }
    return visited;
}

---

💡이진탐색(Binary Search)

📌 개념

• ‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘
• ‘탐색 범위를 절반씩 줄여’나가기 때문에 선형탐색에 비해 빠른 속도를 보장
• 하지만 ‘배열이 정렬되어 있어야 한다는 조건’이 필요하기 때문에 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요

📌 특징

• 반드시 정렬되어 있는 상태에서만 사용 가능
• 배열 또는 이진트리를 이용해 구현 가능
• 시간복잡도 Olog(n)

📌 이진탐색트리란?

• 이진 탐색을 위한 이진트리
• 왼쪽 서브트리 < 루트
• 오른쪽 서브트리 > 루트

📌 반복을 이용한 이진탐색 구현 ★★

int binarySearch2(int key, int low, int high) {
	int mid;

	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1; // 탐색 실패 
}

📌 순환호출을 이용한 이진탐색 구현

int binarySearch1(int key, int low, int high) {
	int mid;

	if(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) { // 탐색 성공 
			return mid;
		} else if(key < arr[mid]) {
			// 왼쪽 부분 arr[0]부터 arr[mid-1]에서의 탐색 
			return binarySearch1(key ,low, mid-1);  
		} else {
			// 오른쪽 부분 - arr[mid+1]부터 arr[high]에서의 탐색 
			return binarySearch1(key, mid+1, high); 
		}
	}

	return -1; // 탐색 실패 
}