[백준] 1260 DFS와 BFS (C++)

 

문제 URL:

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

1260번: DFS와 BFS

 

다음 문제는 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램으로

정점 번호는 1번부터 N번까지지 존재하며 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.

 

이 문제에서 DFS는 재귀호출을, BFS는 큐를 이용하여 구현하였다.

---

#include <iostream>
#include <vector>
#include <algorithm>
#include<queue>
using namespace std;

vector<int> vec[1001];	//이차원 벡터
bool visit[1001] = { false };//방문 판단 배열

//재귀호출 사용
void dfs(int node) {
	cout << node << " ";
	visit[node] = true;
	//이차원 벡터인 vec의 행을 node로 고정시킨 뒤 반복문을 이용하여 vec[node]라는 일차원 벡터의 모든 원소를 돌아봄 
	for (int nextNode : vec[node]) {
		if (!visit[nextNode])	//벡터의 원소(노드)가 방문되지 않을 때만 재귀호출을 해줌(방문된 노드는 이미 출력됨)
			dfs(nextNode);
	}
}

//큐 사용
void bfs(int node) {
	queue<int> q;
	q.push(node);
	visit[node] = true;	//큐에 push된 노드는 방문했다고 여겨줌

	while (!q.empty()) {	//큐가 빌 때까지 반복
		//큐에 들어있는 노드를 출력한 뒤 제거
		node = q.front();
		cout << node << " ";
		q.pop();
		//그 노드에 연결된 다른 노드를 반복문을 이용하여 탐색한 뒤 큐에 넣어줌
		for (int nextNode : vec[node])
			if (!visit[nextNode]) {
				q.push(nextNode);
				visit[nextNode] = true;
			}
	}
}

int main() {
	//정점개수, 간선개수, 탐색시작정점
	int n, m, v;	
	cin >> n >> m >> v;
	
	int a, b;
	//인접리스트 형식으로 수치 삽입
	//ex. 노드1이 있다면 이 1을 a라고 가정하고 1에 연결된 모든 노드를 vec[a]에 삽입(양방향 그래프이기 때문에 vec[b]에도 a 삽입)
	for (int i = 1; i <= m; i++) {	
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)	//정점이 여러개인 경우 작은 번호부터 방문해야하기 때문에 //오름차순으로 정렬
		sort(vec[i].begin(),vec[i].end());

	dfs(v);
	cout << '\n';
	fill_n(visit, 1001, false);	//visit 배열 초기화
	bfs(v);
}