섹션 3. 탐색

DFS(깊이 우선 탐색)

깊이 우선 탐색(DFS : depth-first search)은 그래프 완전 탐색 기법 중 하나로 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

즉 그래프 완적 탐색이라는 기능을 갖고 재귀 함수로 구현을 하며, 스택 자료구조를 이용한다는 특징이 있다. 시간 복잡도는 O(노드수(V) + 엣지 수(E))이다.

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용함으로 스택 오버플로(stack overflow)에 유의해야한다. 응용 할 수 있는 문제로는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬등이 있다.

핵심이론

DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하다. 또한 그래프는 인접 리스트로 표현한다. 그리고 DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하여 주로 설명한다.

DFS를 시작할 노드를 정한 후 사용할 자료구조(인접리스트) 초기화
스택에서 노드를 꺼낸 후 노드의 인접 노드를 다시 스택에 삽입
스택 자료구조에 값이 없을 때까지 반복
1. 이미 다녀간 노드는 방문 배열을 바탕으로 재삽입하지 않는 것이 핵심

Tip) 스택에 노드를 삽입할 때 방문 배열을 체크하고, 스택에서 노드를 뺄 때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조한다.

ex) 신기한 소수 찾기 (백준 2023)

문제 분석
1. 입력의 최대 값이 작다 → 시간 복잡도는 많이 고려할 필요가 없다.
2. DFS는 재귀함수의 형태이다. 재귀 함수에 자릿수 개념을 붙여 구현해본다.
3. 소수의 약수는 1과 자기 자신인 수(에라토스테네스의 체 이용)

#include<iostream>

using namespace std;

static int n;

bool IsPrime(int number) {
	for (int i = 2; i <= number / 2; i++) {
		if (number % i == 0) {
			return false;
		}
	}
	return true;
}

void DFS(int number, int digits) {
	if (digits == n) {
		if (IsPrime(number)) {
			cout << number << '\\n';
		}
		return;
	}
	for (int i = 1; i < 10; i++) {
		if (i % 2 == 0) {
			continue;
		}
		if (IsPrime(number * 10 + i)) {
			DFS(number * 10 + i, digits + 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	DFS(2, 1); //소수, 해당 소수의 자릿수
	DFS(3, 1);
	DFS(5, 1);
	DFS(7, 1);
}

ex) 친구 관계 파악하기 (백준 13023)

문제 분석
1. 다음과 같은 친구 관계를 가진 사람이 존재하는지 구하기
2. N의 최대 범위가 2,000이므로 시간 복잡도 고려시 여유있음
3. 요구하는 A, B, C, D, E의 관계는 재귀 함수의 형태와 비슷
4. 주어진 모든 노드에 DFS를 수행하고 재귀의 깊이가 5이상이면 1 출력
5. DFS의 시간 복잡도는 O(V + E)이므로 그전에 끝나겠지만 최대 4,000, 모든 노드를 진행시 4000 * 2000 즉 800만으로 시간이 남는다.

#include<iostream>
#include<vector>

using namespace std;

static vector <vector<int>> a;
static vector<bool> visited;
static bool arrive;

void DFS(int now, int depth) {
	if (depth == 5 || arrive) {
		arrive = true;
		return;
	}
	visited[now] = true;

	for (int i : a[now]) {
		if (!visited[i]) {
			DFS(i, depth + 1);
		}
	}
	visited[now] = false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	arrive = false;

	cin >> n >> m;

	a.resize(n);

	visited = vector<bool>(n, false);

	for (int i = 0; i < m; i++) {
		int s, e;

		cin >> s >> e;

		a[s].push_back(e);
		a[e].push_back(s);
	}

	for (int i = 0; i < n; i++) {
		DFS(i, 1);
		if (arrive) {
			break;
		}
	}

	if (arrive) {
		cout << "1" << "\\n";
	}
	else {
		cout << "0" << "\\n";
	}
}

BFS (너비 우선 탐색)

너비 우선 탐색(BFS, breadth-first search)은 그래프 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

그래프를 완전 탐색하는 기능을 갖고 있고 FIFO 탐색, Queue 자료구조를 이용한다는 특징을 갖고 있다. 시간 복잡도는 O(V(노드 수)+ E(엣지 수))이다.

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

BFS를 시작한 노드를 정한 후 사용할 자료구조 초기화하기
1. 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크할 배열이 필요하다.
2. 탐색을 위해 스택이 아닌 큐를 사용한다.
큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기
큐 자료구조에 값이 없을 때까지 반복

ex) 트리의 지름 구하기 (백준 1167)

문제 분석
1. 트리는 사이클이 없다.
2. 가장 긴 경로를 찾는 아이디어가 필요하다.
  1. 임의의 노드에서 가장 긴 경로로 연결된 노드는 트리의 지름에 해당하는 두 노드중 하나이다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> edge;

static vector <vector<edge>> a;
static vector <bool>visited;
static vector <int> m_distance;

void BFS(int node) {
	queue<int> myqueue;
	myqueue.push(node);
	visited[node] = true;

	while (!myqueue.empty()) {
		int now_node = myqueue.front();
		myqueue.pop();

		for (edge i : a[now_node]) {
			if (!visited[i.first]) {
				visited[i.first] = true;
				myqueue.push(i.first);
				m_distance[i.first] = m_distance[now_node] + i.second;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	a.resize(n + 1);

	for (int i = 0; i < n; i++) {
		int s;
		cin >> s;

		while (true) {
			int e, v;
			
			cin >> e;

			if (e == -1) {
				break;
			}

			cin >> v;

			a[s].push_back(edge(e, v));
		}
	}

	m_distance = vector<int>(n + 1, 0);
	visited = vector<bool>(n + 1, false);
	BFS(1);

	int max = 1;

	for (int i = 2; i <= n; i++) {
		if (m_distance[max] < m_distance[i]) {
			max = i;
		}
	}

	fill(m_distance.begin(), m_distance.end(), 0);
	fill(visited.begin(), visited.end(), false);

	BFS(max);

	sort(m_distance.begin(), m_distance.end());

	cout << m_distance[n] << "\\n";
}

이진 탐색

이진 탐색(binary search)은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

타깃 데이터를 탐색하는 기능을 갖고 중앙 값 비교를 통한 대상 축소 방식을 특징으로 한다.

시간 복잡도는 O(logN)이다.

이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다. 구현 및 원리가 비교적 간단해서 많은 코딩 테스트에서 부분 문제로 요구된다.

이진 탐색 과정

현재 데이터셋의 중앙값(median)을 선택한다.
중앙값 > 타깃 데이터 인 경우 중앙값 기준으로 왼쪽 데이터셋을 선택
중앙값 < 타깃 데이터 인 경우 중앙값 기준으로 오른쪽 데이터셋을 선택
과정 1, 2, 3을 반복하다가 중앙값 == 타깃 데이터 일때 탐색을 종료

이진 탐색을 사용하면 N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

이진 탐색 데이터는 꼭 정렬되어 있어야 한다.

ex) 16개의 데이터면 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

'알고리즘 > Do it! 알고리즘 코딩테스트 C++' 카테고리의 다른 글

섹션 5. 정수론 (0)	2023.03.30
섹션 4. 탐욕 알고리즘(Greedy Algorithm) (0)	2023.03.29
섹션 2. 정렬(Sorting) (0)	2023.03.27
섹션 1. 자료구조(Data Structure) (0)	2023.03.26
섹션 0. 코딩테스트 준비하기 (0)	2023.03.26

Archive H

섹션 3. 탐색

DFS(깊이 우선 탐색)

BFS (너비 우선 탐색)

이진 탐색

'알고리즘 > Do it! 알고리즘 코딩테스트 C++' 카테고리의 다른 글

댓글

티스토리툴바

섹션 3. 탐색

DFS(깊이 우선 탐색)

BFS (너비 우선 탐색)

이진 탐색

'알고리즘 > Do it! 알고리즘 코딩테스트 C++' 카테고리의 다른 글

관련글

댓글

티스토리툴바