[Argorithm]탐색 알고리즘

📝 개요

탐색 알고리즘 깊이 우선 탐색과 너비 우선 탐색, 이진 탐색에 대해 알아보자

📝 깊이 우선 탐색(DFS)

깊이 우선 탐색은 무엇일까?
DFS는 그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여
최대 깊이까지 탐색을 마친 후 다음 분기로 이동하는 것을 말한다.

 

기능	특징	시간복잡도(노드 = V, 엣지 = E)
그래프 완전 탐색	재귀 함수로 구현 스택 자료구조 이용	O(V + E)

 

깊이 우선 탐색의 핵심 이론

• DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다.
• DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용한다. 

깊이 우선 탐색 응용

• 단절점 찾기
• 단절선 찾기
• 사이클 차기
• 위상 정렬

📌 DFS 사용해보기

1. DFS를 시작할 노드를 정한 후 사용할 자료구조(인접 리스트) 초기화

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기 

먼저 스택에서 POP을 수행해 노드를 꺼낸다. 해당 노드를 탐색 순서에 기입하고 인접 리스트르 ㄹ스택에 삽입하여 방문 배열 처리한다. 

3. 스택에 자료구조 값이 없을 때까지 반복하기 

앞선 과정을 스택 자료구조에 값이 없을 때까지 반복한다. 이때 이미 방문한 노드는 재방문하지 않는다.

[BOJ S2][#DFS]2210번 숫자판 점프 (tistory.com)

[BOJ S2][#DFS]2210번 숫자판 점프

[BOJ S1][#DFS]2667번 단지번호붙이기 (tistory.com)

[BOJ S1][#DFS]2667번 단지번호붙이기

 

📝 너비 우선 탐색(BFS)

너비 우선 탐색은 무엇일까?
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 
가까운 노드를 먼저 방문하면서 탐색한다.

 

기능	특징	시간복잡도(노드 = V, 엣지 = E)
그래프 완전 탐색	FIFO 탐색 Queue 자료구조 이용	O(V + E)

 

너비 우선 탐색 핵심 이론

• 선입선출 방식으로 탐색하므로 큐를 이용해서 구현
• 탐색 시작 노드와 가까운 노드를 우선 탐색하므로 목표 노드에 도착하는 경로가 여러 개 일 때 최단 경로 보장

📌 BFS 사용해보기

1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기

BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하는 배열이 필요

그래프를 인접 리스트로 표현하는 것 역시 DFS와 동일하다.

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

큐에서 노드를 꺼내면서 인접 노드를 큐에 삽입한다. 이때 방문 배열을 체크하여 이미 방문한 노드는 큐에 삽입하지 않는다.

3. 큐 자료구조에 값이 없을 때까지 반복하기 

큐에 노드가 없을 때까지 앞선 과정을 반복하여 모두 확인