[BOJ] 1260 DFS와 BFS C++

개요

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

1260번: DFS와 BFS

실버 2급 DFS와 BFS 기초 문제다.

본문

풀이

인접 리스트 기반(vector)으로 구현했다.

각각 DFS는 stack, BFS는 queue를 사용했다.

정점의 번호가 작은 순으로 탐색하라는 조건이 있기 때문에 리스트(vector)를 정렬해주어야 한다.

DFS는 스택으로 후입선출이기 때문에 내림차순으로,

BFS는 큐로 선입선출이기 때문에 오름차순으로 정렬해주어야 한다.

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
constexpr int RANGE = 1002;

int N, M, V;
vector<int> graph[RANGE];

void dfs() 
{
	bool visit[RANGE]{};
	stack<int> s;
	s.push(V);


	for (int i = 1; i <= N; i++)
		sort(graph[i].rbegin(), graph[i].rend());

	while (!s.empty())
	{
		int v = s.top();
		s.pop();
		if (visit[v]) continue;
		
		visit[v] = true;
		cout << v << " ";

		for (int i = 0; i < graph[v].size(); i++)
			s.push(graph[v][i]);
	}
	cout << "\n";
}
void bfs()
{
	for (int i = 1; i <= N; i++)
		sort(graph[i].begin(), graph[i].end());

	bool visit[RANGE]{};
	queue<int> q;
	q.push(V);


	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		if (visit[v]) continue;

		visit[v] = true;
		cout << v << " ";

		for (int i = 0; i < graph[v].size(); i++)
			q.push(graph[v][i]);
	}
	cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> V;

	for (int i = 1; i <= M; i++) {
		int from, to;
		cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	dfs();
	bfs();
}