백준 1260번: DFS와 BFS (C++)

링크

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

풀이방법

해당 문제는 그래프 관련 dfs와 bfs 기초적인 사용법을 묻는 문제로 기본적인 dfs, bfs지식만 가지면 풀 수 있다 하지만 문제에서 말하는 세 가지 조건을 유의해서 코드를 작성해야한다.

1. 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 
2. 탐색을 시작할 정점의 번호 V가 주어진다. 
3. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 

코드

#include <bits/stdc++.h>
using namespace std;


int n, m;
vector<int> adj[1005];
bool vis[1005];
int v;


void bfs(int v)
{
	queue<int> q;
	q.push(v);
	vis[v] = true;
	cout << v << ' ';

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (auto nxt : adj[cur])
		{
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = true;
			cout << nxt << ' ';
		}
	}
}

void dfs(int v)
{
	vis[v] = true;
	cout << v << ' ';
	for (auto nxt : adj[v])
	{
		if (vis[nxt]) continue;
		dfs(nxt);
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	
	cin >> v;
	int a, b;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		
	}

	for (int i = 1; i <= n; i++)
	{
		sort(adj[i].begin(), adj[i].end());
	}


	dfs(v);
	fill(vis+1, vis + n+1, 0); // [0]~[n]
	cout << '\n';
	bfs(v);

   
}