[C++] 백준 1260 - DFS와 BFS

0. 주어진 문제

DFS와 BFS 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	61214	18052	10649	29.187%

문제

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

입력

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

출력

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

1. 풀이

1) 큐를 활용하여 풀이하려고 하였다.

2) DFS(Depth-First Search) 방식은 방문하지 않은 간선중에 가장 빠른 간선이 나오면 재귀호출을 활용해 계속 깊이가 깊어지는 방식을 활용하였다.

3) BFS(Breadth-First Search) 방식은 인접한 노드를 모두 큐에 추가한 뒤, 큐의 가장 앞부분을 cout를 활용해 출력하며, 아직 방문하지 않은 자식 노드가 있는지 확인을 하는 방식을 선택하였다.

2. 소스코드

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <iostream> #include <queue> #include <cstring>   using namespace std; const int MAX = 1000 + 1;   int adjacent[MAX][MAX]; bool visited[MAX];   queue<int> q;   void DFS(int idx, int node) {     visited[idx] = 1;     cout << idx << " ";     for (int i = 1; i <= node; i++)         if (adjacent[idx][i] && !visited[i])         {             //인접한 노드에 대해서 또 다시 DFS             DFS(i,node);         } }       void BFS(int idx,int node) {     q.push(idx);     visited[idx] = 1;       while (!q.empty())     {         idx = q.front();         q.pop();         cout << idx << " ";         //BFS는 해당 노드에 인접한 노드들을 모두 추가한 뒤 BFS 진행         for (int i = 1; i <= node; i++)             if (adjacent[idx][i] && !visited[i])             {                 visited[i] = 1;                 q.push(i);             }     } }       int main(void)   {     int node, line, start;     cin >> node >> line >> start;     for (int i = 0; i < line; i++)     {         int from, to;         cin >> from >> to;         adjacent[from][to] = 1;         adjacent[to][from] = 1;     }     DFS(start, node);     cout << endl;     memset(visited, false, sizeof(visited));     BFS(start,node);     cout << endl;     return 0; } Colored by Color Scripter

cs

3. 문제 출처

https://www.acmicpc.net/problem/1260

4. 참고

https://twpower.github.io/73-how-to-implement-dfs-and-bfs-in-cpp

https://jaimemin.tistory.com/561