[BOJ / C++] #1260 DFS와 BFS
문제 풀이
기본적인 DFS, BFS 탐색 문제이다.
DFS는 재귀호출, BFS는 큐를 이용해 구현했다.
이때 그래프는 벡터 배열을 이용한 인접리스트로 나타내었고,
두 정점사이에 여러 간선이 있을 수 있으므로 각 배열마다 오름차순으로 정렬해주었다.
방문했는지 검사하는 visited배열 변수도 잊지 말기!
코드
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1001
int N, M, V;
vector<int> map[MAX];
bool visited[MAX];
void dfs(int v){
cout<<v<<" ";
for(int i : map[v]){
if(!visited[i]){
visited[i]=true;
dfs(i);
}
}
}
void bfs(int v){
queue<int> q;
q.push(v);
visited[v]=true;
while(!q.empty()){
int idx=q.front();
q.pop();
cout<<idx<<" ";
for(int i : map[idx]){
if(!visited[i]){
q.push(i);
visited[i]=true;
}
}
}
}
int main(){
cin>>N>>M>>V;
for(int i=0;i<M;i++){
int a, b;
cin>>a>>b; //양방향
map[a].push_back(b);
map[b].push_back(a);
}
for(int i=1;i<=N;i++){
sort(map[i].begin(),map[i].end());
}
visited[V]=true;
dfs(V);
cout<<"\n";
//visited 초기화
memset(visited, false, sizeof(visited));
bfs(V);
cout<<"\n";
return 0;
}
Author And Source
이 문제에 관하여([BOJ / C++] #1260 DFS와 BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/BOJ-C-1260-DFS와-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)