💡 브루트 포스 알고리즘

Brute (무식한) + Force (힘) = 발생할 수 있는 모든 경우를 탐색한다 : 완전 탐색 ➡️ DFS /BFS, 순차 ...

ex) 3자리로 구성된 자물쇠의 비밀번호를 찾기 위해 000 ~ 999까지 모든 경우의 수를 입력해본다. (= 노가다)

🙆🏻 장점

• 확실한 정답을 찾을 수 있다.
• 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

🙅🏻 단점

• 모든 경우를 탐색해야 하므로 시간이 오래 걸리고, 효율적이지 못하다.

📒 순차 탐색 (Sequential Search)

원하는 값을 만날 떄까지 맨 앞부터 순서대로 요소를 검색 : 선형 구조

1. 주어진 문제를 구조화한다.
2. 구조화된 공간을 적절한 방법으로 해를 찾을 때까지 탐색한다.

📝 예제

크기가 5인 배열 a[]에서 값이 3인 요소 찾기

int[] arr = {3, 7, 6, 3, 5};
		
System.out.println("순차 탐색 시작!");

for(int i=0;i<arr.length;i++) {
	if(arr[i] == 3) System.out.println("3의 인덱스 : " + i);
}

System.out.println("순차 탐색 종료!");

: arr[0] ~ arr[4] 까지 모든 경우를 탐색하여 값이 3인 요소의 인덱스 0, 3 반환

📒 너비 우선 탐색 (BFS : Breath-First Search)

출발 노드부터 목표 노트까지 단계별로 횡방향으로 탐색 : 최단 경로

✅ 탐색 순서 : A ➡️ B ➡️ C ➡️ D ➡️ E ➡️ F ➡️ G ➡️ H

🙆🏻 장점

• 출발 노드 ➡️ 목표 노드 간 최단 길이 경로 보장

🙅🏻 단점

• 경로가 긴 경우, 탐색 가지 증가에 따라 비교적 많은 기억 공간 필요
• 무한 그래프일 경우, 해를 찾을 수도 없고 끝낼 수도 없다.

📒 깊이 우선 탐색 (DFS : Depth-First Search)

출발 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색

✅ 탐색 순서 : A ➡️ B ➡️ E ➡️ F ➡️ H ➡️ C ➡️ D ➡️ G

🙆🏻 장점

• 현 경로 상의 노드들만 기억하면 되므로 저장공간의 비교적 적은 기억 공간 필요
• 목표 노드가 깊은 단계에 있을 경우, 해를 빨리 도출할 수 있음

🙅🏻 단점

• 최적의 경로가 아닐 수 있음.
• BFS에 비해 느림.
• 해가 없는 경로 속에 깊이 빠질 수 있음. ➡️ 임의의 깊이까지 탐색하는 방법 사용

📝 예제 : [1260] DFS와 BFS

• BFS : 큐 (Queue) 활용
• DFS : 재귀 함수 활용

(풀이 참고 : https://infodon.tistory.com/96)

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
	
	static int[][] arr;
	static boolean[] check; // 탐색 여부 확인 (탐색했으면 true)
	static int n, m, v;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken()); // 정점
		m = Integer.parseInt(st.nextToken()); // 간선
		v = Integer.parseInt(st.nextToken()); // 출발 노드
		
		arr = new int[n+1][n+1];
		// 인접 행렬
		for(int i=0;i<m;i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
		
        check = new boolean[n+1];
		dfs(v);
		System.out.println();
		
		check = new boolean[n+1];
		bfs(v);
	}
	
	public static void dfs(int v) { // 재귀 함수
		check[v] = true;
		System.out.print(v + " ");
		
		for(int i=0;i<=n;i++) {
			if(arr[v][i] == 1 && !check[i]) dfs(i);
		}
	}
	
	public static void bfs(int v) { // 큐
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(v);
		check[v] = true;
		
		while(!q.isEmpty()) {
			v = q.poll();
			System.out.print(v + " ");
			
			for(int i=1;i<=n;i++) {
				if(arr[v][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
	}
}

🔹 main

✅ 인접 행렬 arr[][] : 연결된 노드(a, b) 간 간선 표현 ➡️ arr[a][b] = arr[b][a] = 1

1 2
1 3
1 4
2 4
3 4

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 정점
m = Integer.parseInt(st.nextToken()); // 간선
v = Integer.parseInt(st.nextToken()); // 출발 노드
		
arr = new int[n+1][n+1];
// 인접 행렬
for(int i=0;i<m;i++){
	st = new StringTokenizer(br.readLine());
	int a = Integer.parseInt(st.nextToken());
	int b = Integer.parseInt(st.nextToken());
			
	arr[a][b] = 1;
	arr[b][a] = 1;
}	

check = new boolean[n+1];
dfs(v);
System.out.println();
		
check = new boolean[n+1];
bfs(v);

🔹 dfs(int v)

✅ 시작점 v를 받아 해당 노드부터 탐색을 시작하므로 check[v]를 true로 바꿔준 후 v를 출력한다.

이후 해당 노드가 포함된 분기를 지나야 하므로 i번 노드가 v번 노드와 연결되어 있으면서 (arr[v][i] = 1) 탐색한 적이 없을 때 (!check[i]) 재귀 함수 dfs(i)를 호출하여 더 깊은 노드로 이동한다.

public static void dfs(int v) { // 재귀 함수
	check[v] = true;
	System.out.print(v + " ");
		
	for(int i=0;i<=n;i++) {
		if(arr[v][i] == 1 && !check[i]) dfs(i);
	}
}

🔹 bfs(int v)

✅ dfs와 마찬가지로 시작점 v를 입력받아 해당 노드부터 탐색을 시작하므로 check[v]를 true로 바꿔주고, 큐를 선언하여 v를 넣어준다.

이후 v에 큐에서 꺼낸 값(먼저 저장한 값)을 저장하고, i번 노드가 v번 노드와 연결되어 있으면서 (arr[v][i] = 1) 탐색한 적이 없을 때 (!check[i]) 큐에 i를 추가하고 check[i]를 true로 바꿔준다. for문이 끝나면 다시 큐의 가장 앞부분 데이터를 꺼낸 후 for문을 반복한다. 해당 과정(while문)을 큐가 빌 때까지 반복해준다.

public static void bfs(int v) { // 큐
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(v);
		check[v] = true;
		
		while(!q.isEmpty()) {
			v = q.poll();
			System.out.print(v + " ");
			
			for(int i=1;i<=n;i++) {
				if(arr[v][i] == 1 && !check[i]) {
					q.add(i);
					check[i] = true;
				}
			}
		}
	}