[Algorithm/Graph] 깊이 우선 탐색(DFS, Depth-First scrach)

깊이 우선 탐색(DFS)

•  깊이 우선 탐색(DFS)는 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.
• 더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다.
• 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다.

DFS 구현

• BFS에서는 방문하지 않은 정점을 저장하기 위해 큐를 사용했다.
  • 큐를 사용하기 때문에 가장 가까이에 있는 정점부터 접근이 가능했다.
• 하지만 DFS는 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하기 때문에, 스택을 사용한다.
  • 후입 선출 속성을 갖는 스택을 사용하기 때문에 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합하다.
• PS에서 그래프를 나타내야하는 경우 인접 행렬 기반으로 구현하는 경우보단 인접 리스트를 사용할 일이 더 많다

에지 리스트를 통한 구현

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <stack>

using namespace std;

template <typename T>
struct Edge
{
	unsigned src;
	unsigned dst;
	T weight;
};

template <typename T>
class Graph
{
public:
	// N개의 정점으로 구성된 그래프
	Graph(unsigned N) : V(N) {}

	// 그래프의 정점 개수 반환
	auto vertices() const { return V; }

	// 전체 에지 리스트 반환
	auto& edges() const { return edge_list; }

	// 정점 v에서 나가는 모든 에지를 반환
	auto edges(unsigned v) const
	{
		vector<Edge<T>> edges_from_v;
		for (auto& e : edge_list)
		{
			if (e.src == v)
				edges_from_v.emplace_back(e);
		}

		return edges_from_v;
	}

	void add_edge(Edge<T>&& e)
	{
		// 에지 양 끝 정점 ID가 유효한지 검사
		if (e.src >= 1 && e.src <= V && e.dst >= 1 && e.dst <= V)
			edge_list.emplace_back(e);
		else
			cerr << "에러: 유효 범위를 벗어난 정점!" << endl;
	}

	// 표준 출력 스트림 지원
	template <typename U>
	friend ostream& operator<< (ostream& os, const Graph<U>& G);

private:
	unsigned V;		// 정점 개수
	vector<Edge<T>> edge_list;
};

template <typename U>
ostream& operator<< (ostream& os, const Graph<U>& G)
{
	for (unsigned i = 1; i < G.vertices(); i++)
	{
		os << i << ":\t";

		auto edges = G.edges(i);
		for (auto& e : edges)
			os << "{" << e.dst << ": " << e.weight << "}, ";

		os << endl;
	}

	return os;
}

template <typename T>
auto create_reference_graph()
{
	Graph<T> G(9);

	map<unsigned, vector<pair<unsigned, T>>> edge_map;
	edge_map[1] = { {2, 0}, {5, 0} };
	edge_map[2] = { {1, 0}, {5, 0}, {4, 0} };
	edge_map[3] = { {4, 0}, {7, 0} };
	edge_map[4] = { {2, 0}, {3, 0}, {5, 0}, {6, 0}, {8, 0} };
	edge_map[5] = { {1, 0}, {2, 0}, {4, 0}, {8, 0} };
	edge_map[6] = { {4, 0}, {7, 0}, {8, 0} };
	edge_map[7] = { {3, 0}, {6, 0} };
	edge_map[8] = { {4, 0}, {5, 0}, {6, 0} };

	for (auto& i : edge_map)
		for (auto& j : i.second)
			G.add_edge(Edge<T>{ i.first, j.first, j.second });

	return G;
}

template <typename T>
auto depth_first_search(const Graph<T>& G, unsigned start)
{
	stack<unsigned> stack;
	set<unsigned> visited;			// 방문한 정점
	vector<unsigned> visit_order;	// 방문 순서
	stack.push(start);

	while (!stack.empty())
	{
		auto current_vertex = stack.top();
		stack.pop();

		// 현재 정점을 이전에 방문하지 않았다면
		if (visited.find(current_vertex) == visited.end())
		{
			visited.insert(current_vertex);
			visit_order.push_back(current_vertex);

			for (auto& e : G.edges(current_vertex))
			{
				// 인접한 정점 중에서 방문하지 않은 정점이 있다면 스택에 추가
				if (visited.find(e.dst) == visited.end())
				{
					stack.push(e.dst);
				}
			}
		}
	}

	return visit_order;
}

int main()
{
	using T = unsigned;

	// 그래프 객체 생성
	auto G = create_reference_graph<T>();
	cout << "[입력 그래프]" << endl;
	cout << G << endl;

	// 1번 정점부터 DFS 실행 & 방문 순서 출력
	cout << "[DFS 방문 순서]" << endl;
	auto dfs_visit_order = depth_first_search(G, 1);
	for (auto v : dfs_visit_order)
		cout << v << endl;
}

 

BFS와 거의 유사하지만, 큐 대신 스택을 사용했다는 점에서 차이가 존재한다.

 

인접 행렬로 DFS 구현

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

// 입력
int board[502][502] =
    {{1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
     {1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
     {1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
     {1, 1, 0, 0, 1, 0, 0, 0, 0, 0},
     {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

// 방문 기록
bool vis[502][502];
int n = 7, m = 10;
// [x][y]라고 생각하고, x를 row, y를 column으로 생각하자
// 아래, 오른쪽, 위, 왼쪽 순서라고 가정
// 아래(x + 1), 오른쪽(x), 위(x - 1), 왼쪽 (x) 
int dx[4] = {1, 0, -1, 0};
// 아래(y), 오른쪽(y + 1), 위(y), 왼쪽(y - 1)
int dy[4] = {0, 1, 0, -1};

// DFS에서는 그래프를 저장할 자료구조(여기서는 NXM 인접 행렬), 방문 기록, 방문할 곳을 저장할 stack 총 3가지가 필요함을 기억하자
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // 방문할 곳을 저장할 stack를 만들자
    stack<pair<int, int>> S;

    // (0, 0)을 반복했다고 명시하고, 아래에서 반복문을 통해 원하는 결과를 얻는다.
    vis[0][0] = 1;
    S.push({0, 0}); // 스택에 시작점을 push

    // 현재 위치를 스택에서 꺼내서 설정해주고, 주변을 순회하며 방문하지 않은 곳이 있으면 방문을 체크하고 스택에 push

    while (!S.empty()) { // 더 이상 방문할 곳이 없을 때 까지
        auto cur = S.top(); // 현재 위치를 얻는다
        S.pop();
        cout << '(' << cur.X << ", " << cur.Y << ") -> "; 
        for (int dir = 0; dir < 4; dir++) { // 인접 행렬 내 현재 위치에서 상하좌우를 살피겠다.
            int nx = cur.X + dx[dir]; // nextX 좌표
            int ny = cur.Y + dy[dir]; // nextY 좌표
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 탐색하는 점이 행렬의 범위를 벗어난 경우
            if (vis[nx][ny] || board[nx][ny] != 1) continue; // 이미 방문한 노드이거나 연결되어 있지 않는 노드인 경우
            vis[nx][ny] = 1; // 이미 방문했다고 명시. 반드시 stack에 push 할 때 같이 방문 기록을 남겨야 함
            S.push({nx, ny});
        }
    }
}

 

인접 리스트로 DFS 구현

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000;

bool vis[MAX];
vector<int> adj[MAX];
stack<int> S;

int main(void) {
    int n, m, start; // n : 노드의 수, m : 간선(에지)의 수, start : 출발점 Index
    cin >> n >> m >> start;
    for (int i = 0; i < m; i++) {
        int s, e;
        cin >> s >> e;
        // 무향 그래프라 양방향으로 push
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
    
    vis[start] = true;
    S.push(start);
    while (!S.empty()) {
        int cur = S.top();
        S.pop();
        cout << cur << " "; // 방문한 노드를 출력합니다.
        
        for (int i = 0; i < adj[cur].size(); i++) { // cur에 연결되어 있는 노드에 대해서 순회
            int next = adj[cur][i];
            if (!vis[next]) {
                vis[next] = true;
                S.push(next);
            }
        }
    }

    return 0;
}