DFS와 BFS를 사용하여 그래프를 검색한 결과를 반환하는 프로그램을 작성하세요. 그러나 여러 정점을 방문할 수 있는 경우 정점 번호가 작은 정점을 먼저 방문하고 더 이상 방문할 정점이 없으면 프로세스를 종료합니다.
정점 번호의 범위는 1에서 N까지입니다.
기입
노드의 수 N(1 ≤ N ≤ 1,000), 간선의 수 M(1 ≤ M ≤ 10,000), 검색을 시작할 노드의 수 V가 첫 번째 줄에 주어집니다.
다음 M 행은 가장자리가 연결되는 두 정점의 번호를 가져옵니다.
두 노드 사이에 여러 에지가 있을 수 있습니다.
입력으로 주어진 에지는 양방향입니다.
누르다
DFS 수행 결과는 첫 번째 행에 인쇄되고 BFS 수행 결과는 다음 행에 인쇄됩니다.
V로 시작하는 방문 지점이 순서대로 표시됩니다.
'추천 관련글,
백준실버2 / dfs and bfs
항상 개념은 알고 있었지만 제대로 문제를 풀 수 있었던 것은 처음이었습니다.
놀랍게도 한시간동안 삽질을 했습니다.
.^^ (날 욕하지마, 그래)
하지만 아무리 열심히 삽질해도 내 뇌리에 단단히 박혀 있었다.
이제 다른 그래프 문제는 쉽게 풀 수 있습니다.
사실
기억해 난 미래의 바보같은 나야
1. bfs는 무조건 queue를 사용하는 것이 기본입니다.
2. dfs 재귀로 해결할 때 전역 변수가 필요합니다.
3. 입력이 수신되면 플로팅 문제를 매트릭스로 저장할 때 나중에 유용합니다.
#include <iostream>
#include <queue>
using namespace std;
int n;
int m;
int v;
int mat(1001)(1001);
int dfs_visited(1002) = {0}; // dfs는 재귀로 풀거라서 전역변수 배열 visited 필요
int dfs(int V){
cout << V << " ";
dfs_visited(V) = 1;
for (int i = 1; i <= n; ++i){
if(dfs_visited(i)==1 || mat(V)(i) == 0) continue; // 이미 방문했거나 mat에 없다면 스킵
// V = i
dfs(i);
}
return 0;
}
int bfs(int V){
int bfs_visited(1002) = {0};
queue<int> q; // bfs는 항상 queue를 사용한다.
q.push(V);
bfs_visited(V) = 1;
while(!
q.empty()){
int x = q.front();
cout << x << " ";
q.pop();
for (int i = 1; i <= n; ++i){
if(bfs_visited(i)==1 || mat(x)(i) == 0) continue; // 이미 방문했거나 mat에 없다면 스킵
q.push(i);
bfs_visited(i) = 1;
}
}
return 0;
}
int main(){
cin >> n >> m >> v;
int x, y;
for (int i = 0; i < m; ++i) {
cin >> x >> y;
mat(x)(y) = mat(y)(x) = 1; // 매트릭스로 그래프 표현
}
int V = v;
dfs(V);
cout << "\n";
bfs(V);
return 0;
}