Study hard
(c++)백준 1260번: DFS와 BFS 본문
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알고리즘
#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;
int N, M, V;
int Graph[1001][1001];//이어진 정점들 1 표시
bool check[1001];
void dfs(int curV) {
check[curV] = true;
cout << curV << ' ';
for (int i = 1; i <= N; i++) {
if (Graph[curV][i] == true && check[i] == false) {
dfs(i);
}
}
}
void bfs() {
queue<int>q;
check[V] = true;
q.push(V);
while (!q.empty()) {
int curV = q.front();
q.pop();
cout << curV << ' ';
for (int i = 1; i <= N; i++) {
if (Graph[curV][i] == true && check[i] == false) {
check[i] = true;
q.push(i);
}
}
}
}
void input() {
cin >> N >> M >> V;
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
Graph[a][b] = 1;
Graph[b][a] = 1;
}
}
void solution() {
input();
dfs(V);
cout << '\n';
memset(check, false, sizeof(check));
bfs();
}
int main() {
solution();
return 0;
}
'백준 > bfs, dfs' 카테고리의 다른 글
(c++) 백준 9466번: 텀 프로젝트 (0) | 2020.06.19 |
---|---|
(c++)백준 2331번: 반복수열 (0) | 2020.06.19 |
(c++)백준 10451번: 순열 사이클 (0) | 2020.06.19 |
(c++)백준 1707번: 이분 그래프 (0) | 2020.06.19 |
(c++)백준 11724번: 연결 요소의 개수 (0) | 2020.06.18 |