Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
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
Archives
Today
Total
관리 메뉴

차근차근

[백준 1260] DFS와 BFS 본문

대학교/Algorithm

[백준 1260] DFS와 BFS

SWKo 2020. 1. 28. 18:39

0. 제목

  • 백준 1260 DFS와 BFS
  • BOJ 1260 DFS와 BFS
  • C++ 1260 DFS와 BFS

1. 문제

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


2. 풀이

  • 먼저 탐색을 완료했는지 여부를 체크하는 checked 배열을 선언한다.
  • 그래프를 생성해줄 때는 vector를 이용해서 선언해준다. 연결되어 있는 점들을 해당 vector에 push_back 해줌으로써 원소로 추가해준다.
  • 그렇게 그래프를 생성한 후 오름차순으로 정렬해주어야 한다. 그 이유는 정점이 여러 개인 경우에 작은 번호부터 먼저 방문하기 때문이다.
  • DFS의 경우에는 이미 탐색 완료를 하였으면 리턴하고 탐색하지 않았으면 탐색상태를 true로 바꿔준 후, 출력해준다. 그리고 그 점에 연결되어 있는 점들을 재귀적으로 다시 탐색한다.
  • BFS의 경우에는 queue를 이용하는데 먼저 queue에 시작점을 넣고 checked 배열을 true로 바꿔준다. 그 후 queue가 빌때까지 다음을 반복한다. 
  • 가장 처음 원소를 pop해준 후, 출력한다. 그 후, 해당 점에 연결되어 있는 점들을 순서대로 q에 넣어준다. 넣은 점들은 모두 탐색완료한 것이기때문에 checked[q에 들어간원소] = true 로 바꾸어준다.
  • DFS 실시한 후 BFS를 하기 전에 반드시 checked 배열의 원소 값들은 모두 false 값으로 초기화 시켜야 한다.
  • #include <queue>를 해주니 #include <vector> 를 하지 않아도 vector 사용이 가능하였다.
  • memset은 <cstring> 라이브러리에 있다. 

3. 코드

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
68
69
70
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int checked[1001];
vector<int> a[1001];
 
void dfs(int start);
void bfs(int start);
 
int main(int argc, const char * argv[]) {
    int N, M, V;
    int j, k;
    
    //그래프 생성
    cin >> N >> M >> V;
    for(int i = 0; i < M; i++){
        cin >> j >> k;
        a[j].push_back(k);
        a[k].push_back(j);
    }
    
    //정점이 여러 개인 경우에 작은 번호부터 먼저 방문하기 때문에 정렬해준다.
    for(int i = 1; i <= N; i++){
        sort(a[i].begin(), a[i].end());
    }
    
    dfs(V);
    cout << '\n';
    memset(checked, 0sizeof(checked));    // #include <cstring>
    bfs(V);
    cout << '\n';
    
    return 0;
}
 
void dfs(int x){
    if(checked[x]) return;
    checked[x] = true;
    cout << x << ' ';
    unsigned long size = a[x].size();
    for(int i = 0; i < size; i++){
        int y = a[x][i];
        dfs(y);
    }
}
 
void bfs(int start){
    queue<int> q;
    q.push(start);
    checked[start] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout << x << " ";
        unsigned long size = a[x].size();
        
        for(int i = 0; i < size; i++){
            int y = a[x][i];
            if(!checked[y]){
                q.push(y);
                checked[y] = true;
            }
        }
    }
}
 
 
Comments