Problem
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번까지!
Solution
#include<iostream>
#include<queue>
using namespace std;
#define MAX 1001
int n, m, v; // 정점의 개수, 간선의 개수, 탐색 시작할 정점 개수
int map[MAX][MAX]; // 인접 행렬 그래프
bool visited[MAX]; // 정점 방문 여부
queue<int> q;
// 정점 방문 여부 초기화 함수
void reset(){
for(int i=1;i<=n;i++){
visited[i]=0;
}
}
// DFS 수행
void DFS(int v){
visited[v]=1;
cout << v << ' ';
for(int i=1;i<=n;i++){
if (map[v][i]==1 && visited[i]==0){
// 현재 정점과 연결되어 있고 방문한 적이 없는 경우
DFS(i);
}
}
}
// BFS 수행
void BFS(int v){
q.push(v);
visited[v]=1;
cout << v << ' ';
while(!q.empty()){
v=q.front();
q.pop();
for(int i=1;i<=n;i++){
if (map[v][i]==1 && visited[i]==0){
// 현재 정점과 연결되어 있고 방문한 적이 없는 경우
q.push(i);
visited[i]=1;
cout << i << ' ';
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> v;
for(int i=0;i<m;i++){
int a, b;
cin >> a >> b;
// 정점 a와 b를 간선으로 연결
map[a][b]=1;
map[b][a]=1;
}
reset();
DFS(v);
cout << '\n';
reset();
BFS(v);
return 0;
}
Reference
https://kimyunseok.tistory.com/26
[C++] 백준 1260번 DFS와 BFS
오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다. DFS란? 깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있
kimyunseok.tistory.com
https://kimyunseok.tistory.com/25
[C++] 벡터 사용 시, () 선언과 [] 선언의 차이
vector 선언 시 []괄호와 ()괄호의 차이가 있다. []괄호로 선언시, 텅 빈 이차원 배열이라고 생각하면 된다. 각 벡터의 인덱스마다 동적으로 크기를 할당할 수 있다. ()괄호로 선언시, 처음에 그 공간
kimyunseok.tistory.com
'코딩 테스트 > 백준 (C++, Python)' 카테고리의 다른 글
cpp) 백준 1541: 잃어버린 괄호 (0) | 2023.06.09 |
---|---|
cpp) 백준 25206: 너의 평점은 (0) | 2023.06.09 |
BFS, DFS 이해하기 (0) | 2023.06.08 |
cpp) 백준 1931: 회의실 배정 (0) | 2023.06.08 |
cpp) 백준 11866: 요세푸스 문제 0 (0) | 2023.06.08 |