[c++/알고리즘] DFS 개념 및 예제

DFS (깊이 우선 탐색)

• 개념:
  • DFS는 시작 노드에서 최대한 멀리 있는 노드까지 먼저 탐색하는 방식입니다.
  • 보통 재귀나 스택 (Stack) 자료 구조를 사용해 탐색하며, 모든 경로 탐색이나 연결 요소 찾기에 유용합니다.
• 동작 원리:
  1. 시작 노드 방문: 시작 노드를 방문하고, 인접한 노드를 재귀적으로 방문합니다.
  2. 재귀로 탐색 진행: 방문하지 않은 인접 노드를 탐색하고, 각 노드에서 더 이상 방문할 노드가 없을 때까지 재귀 호출을 반복합니다.
  3. 재귀 호출 종료: 모든 경로를 다 탐색한 후 재귀 호출이 종료되며 상위 노드로 돌아갑니다.
• DFS 알고리즘의 특징:
  • 깊이 우선 탐색을 수행하여 특정 경로가 존재하는지 확인할 수 있습니다.
  • 재귀 호출의 특성을 이용해 백트래킹 문제에서 유용하게 쓰입니다.
  • 보통 노드의 모든 연결 경로를 탐색하기에 적합합니다.

<DFS 템플릿>

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

vector<int> graph[9];
bool isVisited[9] = { false };

void dfs(int x) {
	isVisited[x] = true;
	cout << x << " ";
	for (int i = 0; i < graph[x].size(); i++) {
		int y = graph[x][i];
		if (!isVisited[y])
			dfs(y);
	}
}

int main() {

	// 노드 1에 연결된 노드 정보 저장
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[1].push_back(8);

	// 노드 2에 연결된 노드 정보 저장 
	graph[2].push_back(1);
	graph[2].push_back(7);

	// 노드 3에 연결된 노드 정보 저장 
	graph[3].push_back(1);
	graph[3].push_back(4);
	graph[3].push_back(5);

	// 노드 4에 연결된 노드 정보 저장 
	graph[4].push_back(3);
	graph[4].push_back(5);

	// 노드 5에 연결된 노드 정보 저장 
	graph[5].push_back(3);
	graph[5].push_back(4);

	// 노드 6에 연결된 노드 정보 저장 
	graph[6].push_back(7);

	// 노드 7에 연결된 노드 정보 저장 
	graph[7].push_back(2);
	graph[7].push_back(6);
	graph[7].push_back(8);

	// 노드 8에 연결된 노드 정보 저장 
	graph[8].push_back(1);
	graph[8].push_back(7);

	dfs(1);
}