[DFS&BFS] 백준 1260번 DFS와 BFS

www.acmicpc.net/problem/1260

 

 

지금 c++ 벡터를 완벽히 숙지하지 못하여 queue는 벡터로 선언하고 map이나 visit은 일반 전역변수로 선언해준 것이 아쉽긴하다. 차차 익혀나가면서 바꾸려고 한다.

DFS는 재귀를 통한 풀이를 하였고, BFS는 큐를 통하여 구현하였다.

 

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;
queue<int> q;
int map[1001][1001];
int visit[1001] = { 0 };
int N, M, V;

void DFS(int V) {
	visit[V] = true;
	cout << V << " ";
	for (int i = 1; i <= N;i++) {
		if (map[V][i] && !visit[i]) {
			DFS(i);
		}
	}
}
void BFS(int V) {
	visit[V] = true;
	q.push(V);
	while (!q.empty()) {
		V = q.front();
		q.pop();
		cout << V << " ";
		for (int i = 1;i <= N;i++) {
			if (map[V][i] && !visit[i]) {
				q.push(i);
				visit[i] = true;
			}
		}
	}
}

int main() {
	int line1, line2;
	memset(visit, 0, sizeof(visit));
	memset(map, 0, sizeof(map));
	cin >> N >> M >> V;
	for (int i = 0; i < M;i++) {
		cin >> line1 >> line2;
		map[line1][line2] = 1;
		map[line2][line1] = 1;
	}
	DFS(V);
	memset(visit, 0, sizeof(visit));
	cout << "\n";
	BFS(V);
	return 0;
}