그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

🔎 문제 파악

📌 DFS와 BFS의 기본적인 구현 형태를 알고 있다면 어렵지 않게 풀 수 있다.

📌 DFS, BFS를 구현할 때는 처음 방문할 vertex와 방문 순서를 확인한다. 이 경우 입력으로 받은 vertex부터 방문을 시작하고 오름차순으로 방문하게 된다.

🔑 DFS

DFS의 기본적인 구현 형태는 다음과 같다.

vector<int>  g[10001];
bool visit[10001];

void dfs(int v) {
	if (!visit[v]) {
		visit[v] = true;

		for (int i = 0;i < g[v].size(); i++) {
			if (!visit[g[v][i]])
				dfs(g[v][i]);
		}
	}
}

🔑 BFS

BFS의 구현형태는 다음과 같다.
DFS에서 시스템 스택을 이용한 것과 다르게 BFS에서는 queue를 사용한다.

vector<int>  g[10001];
bool visit[10001];

void bfs(int v) {
	queue<int> q;
	int now, i, next;

	q.push(v);
	visit[v] = true;
	while (!q.empty()) {
		now = q.front();
		q.pop();

		for (i = 0;i < g[now].size();i++) {
			next = g[now][i];
			if (!visit[next]) {
				visit[next] = true;
				q.push(next);
			}
		}
	}
}

📚 graph 구현

문제에서 주어진 그래프는 undirected graph로 입력의 형태는 다음과 같다.

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

int main(){
	int n, m, s;
	int u, v;
	int i;
	scanf("%d %d %d", &n, &m, &s);

	for (i = 0;i < m;i++) {
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u); //directed graph라면 push_back문이 하나임.
	}

	for (i = 1;i <= n;i++) {
		sort(g[i].begin(), g[i].end()); //연결된 vertex를 오름차순으로 정렬
	}
 }

🚀 최종 코드

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

vector<int> g[10001];
bool visit[10001];

/*
* visit 초기화 함수
*/
void initVisit() {
	for (int i = 0;i < 10001;i++)
		visit[i] = false;
}

void dfs(int v) {
	if (!visit[v]) {
		visit[v] = true;
		printf("%d ", v); //처음 방문한 vertex에 대해서 번호 출력

		for (int i = 0;i < g[v].size(); i++) {
			if (!visit[g[v][i]])
				dfs(g[v][i]);
		}
	}
}

void bfs(int v) {
	queue<int> q;
	int now, i, next;

	q.push(v);
	visit[v] = true;
	while (!q.empty()) {
		now = q.front();
		q.pop();
		printf("%d ", now); //처음 방문한 vertex에 대해서 번호 출력

		for (i = 0;i < g[now].size();i++) {
			next = g[now][i];
			if (!visit[next]) {
				visit[next] = true;
				q.push(next);
			}
		}
	}
}


void baekjoon_1260() {
	int n, m, s;
	int u, v;
	int i;
	scanf("%d %d %d", &n, &m, &s);

	for (i = 0;i < m;i++) {
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}

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

	initVisit();
	dfs(s);
	printf("\n");

	initVisit();
	bfs(s);
}