[코딩테스트] [BOJ1260] DFS와 BFS

문제

https://www.acmicpc.net/problem/1260

---

풀이

1. 이중벡터로 간선 정보를 포함한 그래프를 생성한다

2. 재귀함수로 dfs를 구현
   2-1. 시작 노드를 방문 체크해주고, 탐색한 순서를 저장하는 벡터에 넣어준다
   2-2. 인접한 노드를 순회하며, 방문하지 않은 노드라면 해당 노드를 시작점으로 dfs를 수행한다

3. 큐로 bfs 구현
   3-1. 큐에 시작 노드를 넣고, 방문 체크해준다
   3-2. 큐의 front(현재 노드)를 탐색한 순서를 저장하는 벡터에 넣어주고, pop 해준다
   3-3. 인접한 노드를 순회하며, 방문하지 않은 노드라면 방문 체크를 해준 뒤 큐에 push한다
   3-4. 큐가 빌 때까지 반복

4. 탐색 순서 저장 벡터 bfsResult, dfsResult 출력

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> bfs(vector<vector<int>>& adj, int start)
{
	vector<bool> visited(adj.size(), false);
	vector<int> result;

	queue<int> q;
	visited[start] = true;
	q.push(start);

	while (!q.empty())
	{
		int current = q.front();
		result.push_back(current);
		q.pop();

		for (int next : adj[current])
		{
			if (!visited[next])
			{
				visited[next] = true;
				q.push(next);
			}
		}
	}

	return result;
}

void dfsRecursion(vector<vector<int>>& adj, vector<bool>& visited, int start, vector<int>& result)
{
	visited[start] = true;
	result.push_back(start);

	for (int next : adj[start])
	{
		if (!visited[next])
		{
			dfsRecursion(adj, visited, next, result);
		}
	}
}

vector<int> dfs(vector<vector<int>>& adj, int start)
{
	vector<bool> visited(adj.size(), false);
	vector<int> result;

	dfsRecursion(adj, visited, start, result);
	
	return result;
}

void addEdge(vector<vector<int>>& adj, int left, int right)
{
	adj[left].push_back(right);
	adj[right].push_back(left);
}

int main()
{
	int nodeCount = 0, edgeCount = 0, startNode = 0;
	cin >> nodeCount >> edgeCount >> startNode;
	vector<vector<int>> adj(nodeCount);

	vector<vector<int>> edges(edgeCount, vector<int>(2));
	for (int i = 0; i < edgeCount; i++)
	{
		int left = 0, right = 0;
		cin >> left >> right;

		edges[i][0] = left - 1;
		edges[i][1] = right - 1;
	}

	for (auto& e : edges)
	{
		addEdge(adj, e[0], e[1]);
	}

	for (vector<int>& arr : adj)
	{
		sort(arr.begin(), arr.end());
	}

	vector<int> dfsResult = dfs(adj, startNode - 1);
	for (int i = 0; i < dfsResult.size(); i++)
	{
		cout << dfsResult[i] + 1 << " ";
	}

	cout << "\n";

	vector<int> bfsResult = bfs(adj, startNode - 1);
	for (int i = 0; i < bfsResult.size(); i++)
	{
		cout << bfsResult[i] + 1 << " ";
	}

	return 0;
}