[백준알고리즘] 1260번 : DFS와 BFS #스터디 1주차

문제는 아래 사이트에 들어가면 확인 할 수 있다. 

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

1260번: DFS와 BFS

 

예제 입력을 확인해보면 띄어쓰기로 입력을 구분한다 

첫째 줄에 정점의개수, 간선의 개수, 탐색 시작노드를 입력받아야 한다. 

 

간선의 수만큼 반복해서 두 숫자를 입력한 다음, 두 숫자를 연결해주어야 한다. 

인접리스트를 이용해 연결해주었다. 

 

>> 선언

 

>> 벡터 a를 사용한 연결

 

정렬을 해줌으로서 작은 숫자 먼저 나오는 조건을 성사시켰다. 

 

dfs먼저 출력 후, 방문여부를 초기화 하고 bfs를 출력해주었다. 

 

bfs와 dfs코드는 그래프 구조를 공부하면서 올려놓았다. 

https://jie0025.tistory.com/35

그래프(Graph) 개념과 탐색알고리즘 (BFS 너비우선탐색, DFS 깊이우선탐색)

 

<전체 코드>

 

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

#include <iostream> #include <cstring> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; const int num = 1001; //정점 최대 개수 1000 해주려고 int visit[num]; //정점 스택,큐에 넣었는지 확인 vector<int> a[num]; //인접리스트를 통한 연결 void dfs(int start) {     stack<int> s;     s.push(start);     while (!s.empty()) {         int x = s.top();         s.pop();         if ( visit[x]) continue;         visit[x] = true;         printf("%d ", x);         for (int i = a[x].size() - 1; i >= 0; i--) {             int y = a[x][i];             if (!visit[y]) s.push(y);         }     } } void bfs(int start) {     queue<int> q;     q.push(start);     visit[start] = true;     while (!q.empty()) {         int x = q.front();         q.pop();         printf("%d ", x);         for (int i = 0; i < a[x].size(); i++) {             int y = a[x][i];             if (!visit[y]) {                 q.push(y);                 visit[y] = true;             }         }     } } int main() {     int n, m, v;//정점, 간선, 탐색시작정점번호     cin >> n >> m >> v;     for (int i = 0; i < m; i++) {         int v1, v2;         cin >> v1 >> v2;         a[v1].push_back(v2); //vector의 끝에 value 추가         a[v2].push_back(v1);     }     for (int i = 0; i <= n; i++) {         sort(a[i].begin(),a[i].end());   //정렬     }     dfs(v);     memset(visit, 0, sizeof(visit));     printf("\n");     bfs(v);     return 0; } Colored by Color Scripter

cs