[백준/C++] 1260번 : DFS와 BFS

[백준/C++] 1260번 : DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

풀이

https://dev-minji.tistory.com/76

// 1260번 DFS와 BFS #include #include #include #include using namespace std; #define MAX 10001 int N, M, V; // 정점 개수, 간선 개수, 시작 정점 vector graph[MAX]; // 인접 행렬 그래프 bool isVisited[MAX] = {false, }; // 정점 방문 여부 queue q; // DFS : 방문한 노드에서 아직 방문하지 않은 인접한 노드로 옮겨가는 식 void DFS(int v){ isVisited[v] = true; // 방문 표시 cout << v << " "; for (int i=0; i q; // BFS용 cin >> N >> M >> V; for (int i=0; i> u >> v; graph[u].push_back(v); graph[v].push_back(u); } // sort : 하나의 정점에서 다음을 탐색할 떄 node에 순차적으로 접근해야 함 for (int i=0; i

"; fill_n(isVisited, MAX, false); // 방문 여부 초기화 BFS(V); }

from http://dev-minji.tistory.com/77 by ccl(A) rewrite - 2021-08-24 03:00:40