백준 1260번: DFS와 BFS

 

 

 

DFS와 BFS에 관한 개념문제라고 볼수 있다.

아래 포스팅을 보고 풀었다. 

https://jaimemin.tistory.com/561

백준 1260번 DFS와 BFS

DFS는 재귀를 사용하여 풀었고 BFS는 큐를 사용하여 풀었다. 

 

 

#include <iostream>
#include <queue>
#include <cstring> //memset
using namespace std;

const int MAX = 1000 + 1;

int N, M, V;
int adjacent[MAX][MAX];	// 1이면 연결됨을 의미
bool visited[MAX];
queue<int> q;

// DFS 재귀
void DFS(int v) {
	cout << v << " ";
	
	for (int i = 1; i <= N; i++) {
		// 연결되어있고 방문하지 않은 노드일 때
		if (adjacent[v][i] && !visited[i]) {
			visited[i] = 1;
			DFS(i);
		}
	}
}

// BFS 큐
void BFS(int v)
{
	q.push(v);

	// 시작노드와 가까운 노드부터 차례대로 큐에 넣어짐
	while (!q.empty()) {
		v = q.front(); // 부모노드로 재정의
		q.pop();

		cout << v << " ";

		// 해당 노드에 인접한 노드들을 모두 큐에 넣음
		for (int i = 1; i <= N; i++) {
			if (adjacent[v][i] && !visited[i]) {
				visited[i] = 1;
				q.push(i);
			}
		}
	}
	
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	//cin 실행속도 향상

	cin >> N >> M >> V;

	for (int i = 0; i < M; i++) {
		int from, to;
		cin >> from >> to;
		adjacent[from][to] = 1;
		adjacent[to][from] = 1;
	}

	visited[V] = 1;
	DFS(V);
	cout << endl;

	memset(visited, false, sizeof(visited));
	visited[V] = 1;
	BFS(V);
	cout << endl;
	
	
	return 0;
}