[Do it! 알고리즘 코딩테스트: Chapter 5] 깊이 우선 탐색(Depth-First Search)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

 

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

 DFS(Depth-First Search, 깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 가능한 한 깊이 내려가면서 탐색을 진행한 후, 더 이상 갈 곳이 없으면 되돌아오는 방식으로 동작한다.

 

DFS의 특징

1. 스택(Stack) 또는 재귀(Recursion) 사용
   • 명시적으로 스택을 사용할 수도 있고, 재귀 호출을 이용하여 구현할 수도 있다.
2. 깊이 우선 탐색
   • 한 노드에서 출발하여 갈 수 있는 만큼 깊이 탐색한 후, 막히면 다시 돌아와 다른 경로를 탐색한다.
3. 백트래킹(Backtracking) 기법 활용
   • 가능한 한 깊이 탐색하다가 더 이상 진행할 수 없으면 이전 단계로 돌아가 새로운 경로를 탐색하는 방식이다.
4. 경로 기반 탐색
   • 특정 경로를 찾거나, 모든 가능한 해를 찾는 데 효과적이다.

 

DFS 동작 방식

1. 시작 정점을 방문하고 방문 표시를 한다.
2. 현재 정점에서 방문하지 않은 인접 정점이 있다면, 해당 정점으로 이동하여 다시 DFS를 수행한다.
3. 방문할 수 있는 정점이 더 이상 없으면, 이전 정점으로 되돌아간다.
4. 위 과정을 스택 자료구조에 값이 없을 때까지 반복하여 모든 정점을 탐색한다.

// Baekjoon Online Judge Problem. 11724

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node);

int main() {
	int N, M;

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

	cin >> N >> M;
	vector<vector<int>> graph(N + 1);
	vector<bool> visited(N + 1, false);
	stack<int> s;

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	
	int answer = 0;
	for (int i = 1; i < N + 1; i++) {
		if (visited[i] == false) {
			dfs(graph, visited, i);
			answer++;
		}
	}
	cout << answer;
	return 0;
}

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
	if (visited[node])
		return;

	visited[node] = true;

	for (int neighbor : graph[node]) {
		if (visited[neighbor] == false)
			dfs(graph, visited, neighbor);
	}
}

 

 

// Baekjoon Online Judge Problem. 2023

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void DFS(int node, vector<int>& v, int depth);
int N;

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

	cin >> N;

	vector<int> v;
	int arr[4] = { 2, 3, 5, 7 };

	for (int i : arr) {
		v.push_back(i);
		DFS(i, v, 1);
		v.pop_back();
	}

	return 0;
}

void DFS(int node, vector<int>& v, int depth) {

	if (depth > N)
		return;
	else if (depth < N) {

		int number = 0;
		for (int i = 0; i < v.size(); i++) {
			number += v[i] * pow(10, v.size() - i - 1);
		}

		for (int i = 2; i <= sqrt(number); i++) {
			if (number % i == 0)
				return;
		}

		int arr[5] = { 1, 3, 5, 7, 9 };

		for (int i : arr) {
			v.push_back(i);
			DFS(i, v, depth + 1);
			v.pop_back();
		}
	}
	else {
		int number = 0;
		for (int i = 0; i < v.size(); i++) {
			number += v[i] * pow(10, v.size() - i - 1);
		}

		for (int i = 2; i <= sqrt(number); i++) {
			if (number % i == 0)
				return;
		}
		cout << number << '\n';
		return;
	}
}

 

 

// Baekjoon Online Judge Problem. 13023

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

vector<vector<int>> graph;
vector<int> people;
static bool arrive;
void DFS(int depth, int node);

int main() {

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

	int N, M;
	cin >> N >> M;

	graph = vector<vector<int>>(N);
	people = vector<int>(N, false);

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for (int i = 0; i < N; i++) {
		DFS(1, i);

		if (arrive)
			break;
	}
	
	if (arrive)
		cout << '1';
	else
		cout << '0';

	return 0;
}

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

	for (int i : graph[node]) {
		if (people[i] == false) {
			DFS(depth + 1, i);
		}
	}
	people[node] = false;
}

 

 DFS는 깊이 우선 탐색이므로 언제든지 재귀가 반복함에 따라 depth의 여부를 알 수 있다. 이번 문제는 depth가 5가 되면 1을 출력하고, 아닌 경우에는 0을 출력하는 문제였다. 그리고 모든 경우를 구하기 위해 DFS의 마지막 부분에 방문 여부를 다시 false로 바꿔준다.