[C++][백준 1260][BFS, DFS] DFS와 BFS :: seoftware

 문제 

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

1260번: DFS와 BFS

 소스 

 

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

void ddfs(vector<vector<int>>&vec, int V, int N, vector<bool>& visited) {
	visited[V] = true;
	cout << V << " ";

	for (int i = 1; i <= N; i++) {
		if (!visited[i] && vec[V][i]) {
			ddfs(vec, i, N, visited);
		}
	}
}

void dfs(vector<vector<int>>&vec, int V, int N) {
	vector<bool> visited(N+1, false);
	visited[V] = true;
	cout << V << " ";
	for (int i = 1; i <= N; i++) {
		if (!visited[i] && vec[V][i]) {
			ddfs(vec, i, N, visited);
		}
	}
}

void bfs(vector<vector<int>>&vec, int V, int N) {
	vector<bool> visited(N + 1, false);
	visited[V] = true;
	queue<int> bfs_q;
	bfs_q.push(V);
	while (!bfs_q.empty()) {
		int now = bfs_q.front();
		cout << now << " ";
		bfs_q.pop();
		for (int i = 1; i <= N; i++) {
			if (!visited[i] && vec[now][i]) {
				visited[i] = true;
				bfs_q.push(i);
			}
		}
	}
}


int main(void) {
	int N, M, V;
	cin >> N >> M >> V;

	//2차원 벡터 생성
	vector<vector<int>> vec(N+1, vector<int>(N+1, 0));
	int n = N;
	while (n > 0) {
		vec[n][n] = 1;
		n--;
	}
	while (M > 0) {
		int x, y;
		cin >> x >> y;

		vec[x][y] = 1;
		vec[y][x] = 1;

		M--;
	}

	dfs(vec, V, N);
	cout << endl;
	bfs(vec, V, N);

	return 0;
}

 

 음 dfs와 bfs는 알고리즘 슈도 코드 보면서 익숙해지는게 중요할 것 같다!!

기억할거는 bfs는 큐 사용! dfs는 재귀 호출!!