728x90
반응형
1. 문제
https://www.acmicpc.net/problem/1260
2. 풀이
: 그래프에서의 DFS와 BFS를 구현하여 해결합니다.
3. 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int c[1001];
vector <int> a[1001];
void dfs(int x) {
if(c[x]) return;
c[x] = true;
cout << x << " ";
for(int i=0; i<a[x].size(); i++) {
int y = a[x][i];
dfs(y);
}
}
void bfs(int start) {
queue <int> q;
q.push(start);
c[start] = true;
while(!q.empty()) {
int x = q.front();
q.pop();
cout << x << " ";
for(int i=0; i<a[x].size(); i++) {
int y = a[x][i];
if(!c[y]) {
q.push(y);
c[y] = true;
}
}
}
}
int main(void) {
iostream::sync_with_stdio(false);
cin.tie(NULL);
int n, m, v, x, y;
cin >> n >> m >> v;
for(int i=0; i<m; i++) {
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1; i<=n; i++) {
sort(a[i].begin(), a[i].end());
}
dfs(v);
for(int i=1; i<=n; i++) c[i] = false;
cout << "\n";
bfs(v);
return 0;
}
728x90
반응형
'💡 Problem Solving > Baekjoon' 카테고리의 다른 글
[백준 - 10819] 차이를 최대로 [c++] (0) | 2021.01.14 |
---|---|
[백준 - 11724] 연결 요소의 개수 [C++] (1) | 2020.04.20 |
[백준 - 11403] 경로찾기 [C++] (1) | 2020.04.20 |
[백준 - 1012] 유기농 배추 [C++] (2) | 2020.04.17 |
[백준 - 2667] 단지번호붙이기 [C++] (1) | 2020.04.17 |