BFS 구현(C++)

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

using namespace std;

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


unordered_map<int, vector<int>> adjList;
vector<int> result;

void bfs(int start)
{
	unordered_set<int> visited;
	queue<int> q;

	// 시작 노드 방문
	q.push(start);
	visited.insert(start);
	result.push_back(start);
	
	while (!q.empty())
	{
		int node = q.front();
		q.pop();

		// 현재 노드의 인접 노드 중 아직 방문하지 않은 노드 방문
		for (const auto& neighbor : adjList[node])
		{
			if (visited.find(neighbor) == visited.end())
			{
				q.push(neighbor);
				visited.insert(neighbor);
				result.push_back(neighbor);
			}
		}
	}
}

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

	// 시작 노드부터 bfs 시작
	bfs(start);

	return result;
}

int main()
{
	solution({ {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}, {4, 8}, {5, 8}, {6, 9}, {7, 9} }, 1);

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

	return 0;
}

 

• 인접 리스트를 활용해서 너비 우선 탐색 구현