문제 URL:
https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
다음 문제는 그래프를 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);
}