기술면접 알고리즘 [Graph] : DFS (깊이 우선 탐색)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

DFS (Depth First Search)

DFS 는 깊이 우선탐색으로, 깊이 자료구조 형을 사용하거나, 재귀적으로 방문 체크를 진행하며 구현하면 된다.

포인트는 map 을 이용하여 adjacency list 와 visited 를 처리한 방식이다. 

구체적인 코드는 다음과 같다.

#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <map>

class Graph {

	std::map<int, std::list<int>> g;
	std::map<int, bool> visited;

public:
	void addEdge(int from, int to) {
		g[from].push_back(to);
	}

	void dfs_loop(int st) {

		std::stack<int> s;

		s.push(st);

		int cur;
		while(!s.empty()) {
			cur = s.top();
			visited[cur] = true;
			s.pop();

			std::cout << cur << " ";

			for (int next : g[cur]) {
				if (!visited[next]) {
					s.push(next);
				}
			}

		}
		std::cout << std::endl;
	}

	void dfs_recursive(int st) {
		std::cout << st << " ";
		visited[st] = true;

		for (auto itr = g[st].begin(); itr != g[st].end(); ++itr) {
			if (!visited[*itr]) {
				dfs_recursive(*itr);
			}
		}
	}



};

// Driver Code
int main() {

	Graph g;

	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);

	// g.dfs_loop(2);
	g.dfs_recursive(2);
}