백준 #1260
2022. 8. 23. 22:54ㆍ2022 땅울림 썸머코딩
★☆☆☆☆☆☆☆☆☆
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
문제 접근방법
단순하게 DFS와 BFS를 구현하면 되는 문제여서 바로 실행에 옮겼다.
#include<iostream>
#include<queue>
using namespace std;
vector<bool>check_dfs(1001);
vector<bool>check_bfs(1001);
queue<int>Q;
int N, M, V;
bool arr[1001][1001];
void dfs(int vertex) {
check_dfs[vertex] = true;
cout << vertex << " ";
for (int i = 1; i <=1000 ; i++) {
if (arr[vertex][i]) {
if (!check_dfs[i]) {
dfs(i);
}
}
}
}
void bfs(int vertex) {
check_bfs[vertex] = true;
Q.push(vertex);
while (!Q.empty()) {
int temp = Q.front();
Q.pop();
cout << temp << " ";
for (int i = 1; i <= 1000; i++) {
if (arr[temp][i]) {
if (!check_bfs[i]) {
Q.push(i);
check_bfs[i]=true;
}
}
}
}
}
int main() {
cin >> N >> M >> V;
int x, y;
for (int i = 0; i < M; i++) {
cin >> x >> y;
arr[x][y] = true;
arr[y][x] = true;
}
dfs(V);
cout << "\n";
bfs(V);
cout << "\n";
}