DFS 구현 (C++)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
* 깊이 우선 탐색으로 모든 그래프의 노드를 순회하는 함수 solution()을 작성하시오
* 시작노드는 문자형 start로 주어집니다. graph 배열은 [출발 노드, 도착 노드] 쌍들이 들어있는 배열입니다.
* 반환값은 그래프의 시작 노드부터 모든 노드를 깊이 우선 탐색으로 탐색한 경로가 순서대로 저장된 배열입니다.
*/

unordered_map<char, vector<char>> adjList;
vector<char> result;
unordered_set<char> visited;

void dfs(char node)
{
	// 현재 노드를 방문 목록과 방문 경로에 추가
	visited.insert(node);
	result.push_back(node);

	// 현재 노드와 인접한 노드 중, 방문하지 않은 노드에 깊이 우선 탐색을 계속 진행
	for (const auto& neighbor : adjList[node])
	{
		if (visited.find(neighbor) == visited.end())
		{
			dfs(neighbor);
		}
	}
}

vector<char> solution(vector<pair<char, char>> graph, char start)
{
	// 인접 리스트 생성
	for (const auto& edge : graph)
	{
		char first = edge.first;
		char second = edge.second;
		adjList[first].push_back(second);
	}

	// 시작 노드부터 dfs 시작
	dfs(start);
	return result;
}

int main()
{
	solution({ {'A', 'B'}, {'A', 'C'}, {'B', 'D'}, {'B', 'E'}, {'C', 'F'}, {'E', 'F'} }, 'A');

	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << " " ;
	}
	
	return 0;
}

 

• 재귀 함수를 이용한 깊이 우선 탐색
• 중복 방문을 하지 않도록 unorderd_set 을 이용한 방문 체크