백준 1260 DFS와 BFS C++ [컴공과고씨]

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

1260번: DFS와 BFS

일단 문제 제목에 나와있듯이 DFS 깊이 우선 탐색과 BFS 넓이 우선탐색을 구현 해주면 되는 문제이다.

DFS의 쉽게 이해하자면 먼저 쭉쭉쭉 간다고 생각하면 편하다. 

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

무슨 말이냐면 위 표에서 1번에서 16번 가는 길을 찾으려고 할 때 DFS는 어떤식으로 탐색을 하냐면

일단 최대한 16까지 갈 수 있는데 까지 들어간다 즉 1 - 2 - 3 - 4 - 8 - 12 -16 그리고 16에서 도달하기전 12 쪽에서 다시 탐색 시작 이렇게 16까지 쭉 들어가는 모습을 볼 수 있다.

반면 BFS는 천천히 갈 수 있는 곳을 하나씩 탐색 하면서 간다고 생각하면 된다.

1에서 갈 수 있는 곳은? 2 ,5 그 다음 2에서 갈 수 있는 곳 탐색, 5에서 갈 수 있는 곳 탐색 -> 3,6,9가 나오면 또 3,6,9에서 갈 수 있는 곳 탐색 이런식으로 갈 수 있는 곳을 하나씩 탐색하며 간다. 즉 DFS는 결과까지 직행 하고 보고 BFS는 가는 도중 갈 수 있는 곳을 탐색하며 가는 방식이다.

 

위 문제는 간선과 정점이 주어지고 그에 따른 BFS DFS를 구현하는 것이다.

그렇다면 아까 말했듯이 DFS는 길이 연결 되어있으면 쭉쭉쭉 갈 수 있는 곳 까지 갈 것이고 BFS는 주변의 연결 되어있는 정점을 탐색하며 범위를 넓혀가며 가는 것이다.

 

DFS는 재귀함수를 이용하여 BFS는 큐함수를 이용하여로 구현해주었다.

 

전체 코드

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
 
vector<int> vec[10002];
vector<int> result_bfs;
vector<int> result_dfs;
bool visit[1002];
 
void bfs(int temp){
    queue<int> q;
    q.push(temp);
    visit[temp] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        result_bfs.push_back(x);
 
        for (int i = 0; i < vec[x].size(); i++){
            if(!visit[vec[x][i]]){ //방문하지 않은 곳만 탐색
                q.push(vec[x][i]); 
                visit[vec[x][i]] = true;
            }
        }
    }
}
 
void dfs(int x){
    visit[x] = true;
    result_dfs.push_back(x);
 
    for (int i = 0; i < vec[x].size(); i++){
        if(!visit[vec[x][i]]){ //방문하지 않은 곳만 탐색
            dfs(vec[x][i]);
        }
    }
}
 
int main(){
    int n, m, v, a, b;
    cin >> n >> m >> v;
 
    for (int i = 1; i <= m;i++){
        cin >> a >> b;
        vec[a].push_back(b); //양방향 간선처리
        vec[b].push_back(a); //양방향 간선처리
    }
    for (int i = 1; i <= n;i++){
        sort(vec[i].begin(), vec[i].end()); // 낮은 숫자부터 탐색.
    }
    bfs(v);
    memset(visit, false, sizeof(visit));
    dfs(v);
    for (int i = 0; i < result_dfs.size() ;i++){
        cout << result_dfs[i] << " ";
    }
    cout << '\n';
    for (int i = 0; i < result_bfs.size() ;i++){
        cout << result_bfs[i] << " ";
    }
    
    return 0;
}

사용 문법 : DFS, BFS

 

yea!