[BOJ] 1260. DFS와 BFS

풀이

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>

using namespace std;

int N;
int M;
int start;

vector<int> v[1001];
int is_visit[1001];

void dfs(int n);
void bfs(int n);

int main(){
	cin >> N >> M >> start;
	for(int i = 1; i <= M; i++){
		int n1, n2;
		cin >> n1 >> n2;
		v[n1].push_back(n2);
		v[n2].push_back(n1);
	}

	for(int i = 1; i <= N; i++){
		if (v[i].size() != 0){
			sort(v[i].begin(), v[i].end());
		}
	}

	memset(is_visit, 0, sizeof(is_visit));
	dfs(start);

	memset(is_visit, 0, sizeof(is_visit));
	bfs(start);
}


void dfs(int n){
	if (is_visit[n]) return;

	is_visit[n] = 1;
	cout << n << endl;

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

void bfs(int n){
	queue<int> Q;
	Q.push(n);
	is_visit[n] = 1;

	while(!Q.empty()){
		int n = Q.front();
		cout << n << endl;
		Q.pop();

		for(int i = 0; i < v[n].size(); i++){
			if (!is_visit[v[n][i]]){
				Q.push(v[n][i]);
				is_visit[v[n][i]] = 1;
			}
		}
	}
}

DFS와 BFS를 얼마나 기억하는지 자체적으로 테스트 하기 위해 지난번에 풀었던 문제부터 다시 풀고 있다.
전보다 생각하는 게 조금 간결해진 것 같다.
STL은 다 까먹었지만!