[백준 1260번 C++] DFS와 BFS

DFS와 BFS를 기본적으로 알 수 있었던 문제.

BFS의 경우 Queue, DFS의 경우 재귀함수를 사용하여 구현하였다.

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

Cheak Point
1. BFS 구현 시 Queue에 vertex를 삽입할 때에도 방문 표시를 하는 것을 잊지말자!
2.  각 vertex의 인접 node에 방문할 때 해당 for loop를 해당 vertex의 리스트 사이즈까지 하는 것을 잊지말자! 
3. vertex를 방문할 때 두번 방문하지 않도록 bool 타입의 visited를 선언하고, 양방향 그래프의 경우 양쪽 모두 간선을 저장하도록 하자.

 

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
int N, M, V;
vector<int> Graph[1001];
queue<int> Q;
bool visited[1001];

 void DFS(int v) {
	
	visited[v] = true;
	cout << v << " ";

	for (int i = 0; i < Graph[v].size(); i++) {
		//printf("%d", Graph[v][i]);
		if (!visited[Graph[v][i]]) {
			DFS(Graph[v][i]);
		}
	}
}

 void BFS(int v){

	Q.push(v);

	while (!Q.empty()) {
		int v = Q.front();
		visited[v] = true;

		Q.pop();
		cout << v << " ";

		for (int i = 0; i < Graph[v].size(); i++) {
			if (!visited[Graph[v][i]]) {
				Q.push(Graph[v][i]);
				visited[Graph[v][i]] = true; // 이미 queue 에 넣은 원소는 true 처리로 다시 방문하지 않도록 한다!!
			}
		}
	}
}

int main(){
	int v1, v2;
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M >> V;

	for (int i = 1; i <= M; i++) {
		cin >> v1 >> v2;
		Graph[v1].push_back(v2);
		Graph[v2].push_back(v1);
	}

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

	DFS(V);
	cout << "\n";
	memset(visited, false, sizeof(visited));
	BFS(V);
}