[알고리즘] 깊이 우선 탐색 (DFS)

치치·2025년 1월 23일
알고리즘

알고리즘C++

목록 보기
15/24
post-thumbnail

깊이 우선 탐색

  • root 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘이다

  • 깊이 우선 탐색은 스택 자료구조나 재귀를 사용한다

  • 깊이 우선 탐색은 무방향 그래프에서 사용한다

간단하게 보면, root노드부터 시작해서 출력하고 방문체크를 하는 과정을 한다.
현재 노드의 인접한 노드들 중 방문되지 않은 노드가 있다면 그 노드쪽으로 들어가는 것

  • 아래의 그래프를 사용해서 깊이 우선 탐색을 진행해보자

그래프 탐색 예시

1. 그래프 클래스를 생성한다

  • 해당 노드들이 방문되었는지를 확인하기 위한 방문배열 생성
    -> 방문배열이 없으면 재귀를 탈출하지 못하고 무한루프에 빠질 수 있다

  • 그래프들의 정점과 간선을 담아줄 vector배열을 생성

  • 생성자에 방문배열을 모두 초기화한다

#include <iostream>
#include <vector>
#define SIZE 8
using namespace std;

class Graph
{
private:
	bool visited[SIZE]; // 방문 배열
	 
	vector<int> graph[SIZE]; // 정점의 집합 (그래프)

public:
	Graph()
	{
		// 방문 배열 초기화
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = NULL;
		}
	}

  • 여기서 방문배열은 해당 정점이 방문되었는지 아닌지를 체크하기 위한 (T/F) 판단용이다
    -> 정점의 숫자와 방문배열의 인덱스를 같게 하는게 일반적이다
    -> ex) 정점1이 방문되었다면 visited[1]에 True
    -> 아래의 코드에서는 SIZE값이 8이고 정점이 7이기 때문에 [0]인덱스는 사용하지 않고있음

  • vector <int graph[SIZE]는 크기가 SIZE인 배열을 선언한 것이다
    -> 각 인덱스마다 vector<int가 가 들어있고 각 인덱스는 정점을 의미한다
    -> 정점에 push_back을 사용해서 벡터에 연결된 간선들(연결된 다른 정점들)을 저장한다


2. 정점끼리 간선을 연결해주기

// 정점에 간선들 연결해주기
// 해당 인덱스(정점)마다 연결된 간선들
// (연결된 다른 정점들)을 저장할 수 있다
void Insert(int vertex, int edge)
{
	// 무방향 그래프
	graph[vertex].push_back(edge);
	graph[edge].push_back(vertex);
}

  • 각각의 정점들은 원소 수와 동일하게 [1] ~[7]이다

  • 인자로 들어오는 vertex는 정점의 인덱스 번호

  • edge는 내가 간선으로 연결할 정점
    -> 간선을 연결시켜주면 각각의 정점 내에 들어있는 벡터배열에 연결된 정점이 저장되는 것
    -> 무방향 그래프이기 때문에 반대 정점에서도 연결시켜줘야한다

무방향 그래프와 양방향 그래프의 차이점이 뭘까?

  • 무방향 그래프 : 간선의 방향이 없다
    A -> B 와 B -> A가 동일한 간선으로 취급된다
  • 양방향 그래프 : 한 간선이 두 정점을 서로 연결할 때, 두 정점 사이 이동이 양방향으로 가능하다
    -> 즉, 양방향 연결은 무방향 그래프의 특성으로 각 간선의 성질을 의미한다

3. 깊이 우선 탐색 시작

1. 재귀함수 사용

// 깊이 우선 탐색 (재귀 사용)
void Search(int start)
{
	visited[start] = true;

	cout << start << " ";

	for (int i = 0; i < graph[start].size(); i++)
	{
		int next = graph[start][i];

		if (visited[next] == false)
		{
			Search(next);
		}
	}
}

  1. start부터 방문한 뒤 방문체크하기

  2. 해당 정점의 값을 출력하기

  3. 해당 정점과 연결된 다른 정점들을 찾아서 방문하지 않은 정점이라면 그 정점으로 재귀함수 호출

  4. 재귀를 진행하면서 방문체크가 다 되어 더이상 방문되지 않은 정점이 없을 경우, 함수도 종료되고 이전 함수로 이동한다
    -> 계속 진행하다보면 이전에 호출한 함수가 아직 반복문 로직이 다 완료되지 않았었지만, 이미 앞에 재귀로 호출한 함수에서 방문체크가 되어버려 따로 재귀를 또 호출 할 필요가 없어지고 종료된다
    -> 연결된 정점이 이전에 재귀로 호출하여 방문체크가 되었다면 조건문이 만족하지 않아 그냥 건너뛰고 다른 연결된 정점을 확인한다



  • 재귀함수 호출 순서 (출력 순서)
    -> 함수를 호출하면 방문체크한 뒤 바로 출력부터 되기 때문에 출력 순서와 같음
    1 -> 2 -> 3 -> 6 -> 7 -> 4 -> 5

  • 함수 종료 순서
    7 -> 6 -> 3 -> 5 -> 4 -> 2 -> 1


깊이우선탐색 재귀 전체코드

#include <iostream>
#include <vector>
#define SIZE 8
using namespace std;

class Graph
{
private:
	bool visited[SIZE]; // 방문 배열
	 
	vector<int> graph[SIZE]; // 정점의 집합 (그래프)

public:
	Graph()
	{
		// 방문 배열 초기화
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = NULL;
		}
	}

	// 정점에 간선들 연결해주기
	// 해당 인덱스(정점)마다 연결된 간선들(연결된 다른 정점들)을 저장할 수 있다
	void Insert(int vertex, int edge)
	{
		// 무방향 그래프
		graph[vertex].push_back(edge);
		graph[edge].push_back(vertex);
	}

	// 깊이 우선 탐색 (재귀 사용)
	void Search(int start)
	{
		// 현재 노드를 방문한 것으로 표시합니다.
		visited[start] = true;

		// 현재 노드를 출력합니다.
		cout << start << " ";


		// 현재 노드와 연결된 다른 노드를 재귀적으로 방문합니다.
		for (int i = 0; i < graph[start].size(); i++)
		{
			// 현재 노드와 연결된 다음 노드를 가져옵니다.
			int next = graph[start][i];

			if (visited[next] == false)
			{
				// 다음 노드가 방문하지 않은 노드라면 'Search'함수를 호출합니다.
				Search(next);
			}
		}
	}
};



int main()
{
#pragma region 깊이 우선 탐색 (Depth First Search)
	// root 노드에서 시작해서 다음 분기로 넘어가기 전에 
	// 해당 분기를 완벽하게 탐색하는 방법입니다.

	// 깊이 우선 탐색은 스택 자료 구조를 사용합니다.

	// 1. 시작 노드를 스택에 넣고 방문 처리를 합니다.

	// 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면
	//    그 노드를 스택에 넣고 방문 처리합니다.

	// 3. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.

	// 4. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

	Graph graph;

	graph.Insert(1, 2);
	graph.Insert(1, 3);

	graph.Insert(2, 3);
	graph.Insert(2, 4);
	graph.Insert(2, 5);

	graph.Insert(3, 6);
	graph.Insert(3, 7);

	graph.Insert(4, 5);
	graph.Insert(6, 7);

	graph.Search(1);
#pragma endregion


	return 0;
}

출력값 :


2. 스택 자료구조 사용
1. 재귀와 비슷하게 진행되는데, start정점을 스택에 넣고 방문체크를 한다

  1. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣은 뒤 방문체크
  2. 방문 하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다
  3. 2번 과정을 수행할 수 없을 때까지 반복한다

DFS 시간복잡도

시간복잡도 : O(V + E)
-> 그래프의 모든 정점과 간선을 한 번씩만 처리하기 때문
공간복잡도 : O(V)
-> 각 정점에 대한 정보를 저장하기 때문


깊이 우선 탐색 (DFS) 다시보기

#include <iostream>
#include <vector>
#define SIZE 8 // 정점의 갯수 7 + 1
using namespace std;

// 깊이 우선 탐색 DFS
// 무방향 그래프에서 사용된다 
// 방문체크 한 뒤 인접한 노드들 중 방문하지 않은 노드를 탐색한다 
// 재귀를 사용 & 들어갔다가 다시 되돌아와서 탐색한다 (백트래킹느낌?)
// 재귀로써 함수가 종료되면 이전에 호출한 함수로 돌아온다
class Graph
{
private:
	bool visited[SIZE]; // 방문 배열

	// SIZE 크기의 vector<int> 배열
	vector <int> graph[SIZE]; // 그래프 인접리스트

public:
	Graph()
	{
		for (int i = 0; i < SIZE; i++)
		{
			visited[i] = false;
		}
	}
	// 그래프 정점 연결
	void Insert(int x, int y)
	{
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	void Search(int start)
	{
		// 1. 방문체크
		visited[start] = true;

		cout << start << " ";

		// 2. 해당 정점과 연결된 정점들 탐색
		for (int i = 0; i < graph[start].size(); i++)
		{
			int next = graph[start][i];

			if (visited[next] == false)
			{
				Search(next);
			}
		}
	}

};


int main()
{
	Graph graph;

	graph.Insert(1, 2);
	graph.Insert(1, 3);

	graph.Insert(2, 3);

	graph.Insert(2, 4);
	graph.Insert(2, 5);

	graph.Insert(4, 5);

	graph.Insert(3, 6);
	graph.Insert(3, 7);
	
	graph.Insert(6, 7);

	graph.Search(1);

	return 0;
}

결과값:

profile
치치
뉴비 개발자
이전 포스트

[알고리즘] Back tracking (보충)

다음 포스트

[알고리즘] 너비 우선 탐색 (BFS)

0개의 댓글