일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 레벨2
- 코딩테스트
- 문자열
- BFS
- Sort
- 삼성
- 프로그래머스
- 모의SW역량테스트
- dp
- STL
- 2018
- 백준
- 레벨3
- 브루트포스
- 삼성SW테스트
- 이런게4문제
- 완전탐색
- KAKAO
- C++
- swea
- 삼성SW역량테스트
- substr
- Set
- find
- 코딩스킬
- Map
- 백트래킹
- 시뮬레이션
- dfs
- priority_queue
- Today
- Total
-
[BOJ-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
BFS와 DFS 완전탐색에 대한 그래프 문제다.
BFS/DFS에 대한 개념을 잡게해주는 문제였다. 깊이우선 탐색과 너비우선 탐색. 각각의 성격에 대해 통찰을 얻을 수 있었다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define maxVirtex 1000+1
using namespace std;
vector Adj[maxVirtex];
bool check[maxVirtex];
void falsing(){
for(int i=0; i<maxVirtex; i++)
check[i] = false;
}
void dfs(int start){
cout << start << " ";
check[start] = true;
for(int i=0; i<Adj[start].size(); i++){
int curSearch = Adj[start][i];
if(!check[curSearch]){
check[curSearch] = true;
dfs(curSearch);
}
}
}
void bfs(int start){
queue q;
check[start] = true;
q.push(start);
while(!q.empty()){
int front = q.front();
q.pop();
cout << front << " ";
for(int i=0; i<Adj[front].size(); i++){
int y = Adj[front][i];
if(!check[y]){
check[y] = true;
q.push(y);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M, V;
int a, b;
cin >> N >> M >> V;
for(int i=0; i<M; i++){
cin >> a >> b;
Adj[a].push_back(b);
Adj[b].push_back(a);
}
for(int i=1; i<maxVirtex; i++)
sort(Adj[i].begin(), Adj[i].end());
falsing();
dfs(V);
cout << '\n';
falsing();
bfs(V);
cout << '\n';
return 0;
}
'3. DFS & 백트래킹' 카테고리의 다른 글
[DFS] 백준 2468번 - 안전영역 (정답률 33%) (0) | 2020.01.13 |
---|---|
[DFS] 백준 2583번 - 영역 구하기 (정답률 56%) (0) | 2020.01.13 |
[DFS] 백준 2667번 - 단지번호붙이기 (정답률 38%) (0) | 2020.01.07 |
[DFS] 백준 1012번 - 유기농 배추 (정답률 34%) (0) | 2020.01.07 |
[DFS] 백준 11403번 - 경로 찾기 (정답률 51%) (0) | 2020.01.07 |