DFS와 BFS [C++]

문제 링크: https://www.acmicpc.net/problem/1260

난이도: ⚪⚪

문제 설명

문제 접근

1. DFS는 재귀를 이용하고, BFS는 queue자료형을 이용하여 구현한다.
2. 정점 번호가 작은 것을 먼저 방문하기 때문에 연결된 정점들을 정렬한다.
3. 두 정점 사이에 여러 간선이 있을 수 있고, 양뱡향임을 유의한다.
   
   

제출 코드

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

// Graph는 2차원 배열, 방문 노드는 bool 배열로 구현
vector<int> graph[1001];
bool visited[1001];

// dfs(깊이 우선 탐색) 구현
void dfs(int node)
{
	// 방문을 기록한다.
	visited[node] = true;
	cout << node << " ";

	// 입력받은 node에 연결된 정점마다 방문했는지 확인하고 방문하지 않았다면 재귀적으로 반복한다.
	for (int i = 0; i < graph[node].size(); i++)
		if (!visited[graph[node][i]])
			dfs(graph[node][i]);
}

// bfs(너비 우선 탐색) 구현 
void bfs(int node)
{
	// 방문을 기록한다.
	visited[node] = true;
	cout << node << " ";
	
    // 방문한 정점은 큐에 넣는다.
	queue<int> q;
	q.push(node);

	// 큐가 비워질때까지 반복한다.
	while (!q.empty())
	{
    	// 현재 정점을 기록후 큐에서 제거한다.
		int cur_node = q.front();
		q.pop();
		
        // 현재 정점에 연결된 정점들을 순회하며 방문을 기록한다.
		for (int i = 0; i < graph[cur_node].size(); i++)
		{
			if (visited[graph[cur_node][i]] == false)
			{
				visited[graph[cur_node][i]] = true;
				cout << graph[cur_node][i] << " ";
				q.push(graph[cur_node][i]);
			}
		}
	}
}

int main(void)
{
	int N, M, V;
	cin >> N >> M >> V;
	
    // 그래프를 양뱡향으로 채워준다.
	for (int i = 0; i < M; i++)
	{
		int node1, node2;
		cin >> node1 >> node2;
		graph[node1].push_back(node2);
		graph[node2].push_back(node1);
	}
	
    // 연결된 정점이 여러개일 경우 작은 정점부터 탐색하기 때문에 정렬한다.
	for (int i = 0; i < N; i++)
		sort(graph[i + 1].begin(), graph[i + 1].end());

	dfs(V);
	 
    // dfs 탐색 후 사용한 visited를 초기화
	for (int i = 0; i < sizeof(visited); i++)
		visited[i] = false;
	cout << '\n';

	bfs(V);

	return 0;
}

결과