[c++] 백준 1260 DFS와 BFS

백준 단계별로 풀어보기 [DFS와 BFS] DFS와 BFS

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

1260번: DFS와 BFS

 

[풀이]

DFS는 재귀를 이용해서, BFS는 큐를 이용해서 구현하였다. 무방향 그래프이기 때문에 인접행렬을 이용해서 인접관계를 표현했고, 같은 isVisited 배열을 이용하기 때문에 BFS 탐색 이전에 다시 초기화를 해주는 작업이 필요하다.

 

[코드]

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

int n, m, v; //정점의 개수, 간선의 개수, 시작 정점
int adj[1001][1001];
bool isVisited[1001] = { false, };
queue<int> q;

void dfs(int v) {

	isVisited[v] = true;
	cout << v <<" ";

	for (int i = 1; i <= n; i++)
		if (adj[v][i] == 1 && !isVisited[i])
			dfs(i);
		
}

void bfs(int v) {
	q.push(v);
	isVisited[v] = true;

	while (!q.empty()) {
		int v = q.front();
		cout << v << " ";
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (adj[v][i] == 1 && !isVisited[i]) {
				q.push(i);
				isVisited[i] = true;
			}
		}
	}

}

int main() {
	//bfs와 dfs
	
	cin >> n >> m >> v;

	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		adj[a][b] = 1;
		adj[b][a] = 1;
	}

	dfs(v);

	for (int i = 0; i <= 1001; i++) {
		if (isVisited[i])
			isVisited[i] = false;
	}
	cout << "\n";

	bfs(v);

	return 0;
}