백준 | 1260. DFS와 BFS

1. DFS

• 예전에 바이러스 문제 푼거랑 비슷하게 풀었다.
• 1부터 시작한다고 치면 1이랑 연결된거 가서 그 연결된거에 또 연결된거 보고....다 보면 다시 1에 연결된 다음꺼 보고 이런 식으로

void DFS(vector<vector<int>>& grap, vector<bool>& visit, int st){
    visit[st] = true; // 정점 방문처리

    for(int x:grap[st]){ // 정점이랑 연결된 애들 탐색
        if(!visit[x]){ // 연결된 정점이 방문한 애가 아니면
            cout << x << " "; // 출력하고
            DFS(grap, visit, x); // dfs 돌면서 연결된 그 정점으로 넘어가기
        }
    }
    return;
}

 

 

 

2. BFS

• queue 만들어서 시작점이랑 연결된 애 쭉 보면서 연결된 애들 저장+출력
• 저장된거 앞에서부터 하나씩 돌면서 탐색

void BFS(vector<vector<int>>& grap, vector<bool>& visit, int st){
    queue<int>check;
    check.push(st); // queue 시작점

    while(!check.empty()){
        int next = check.front();
        check.pop();

        for(int x: grap[next]){ // 정점이랑 연결된 애들 탐색
            if(visit[x]){ // 연결된 정점이 방문한 애가 아니면
                cout << x << " "; // 출력하고 
                visit[x] = false; // 방문처리
                check.push(x);
            }
        }
    } // 연결된 애들 다 봤으면 처음 연결되어있던 정점이랑 연결된애들 보러 넘어가기
    return;
}

 DFS랑 BFS를 연달아 실행하기 때문에 visit을 1이 미방문 0이 방문으로 처리함.

DFS랑 동일하게 방문처리 사용하고 싶으면 visit 배열을 초기화하고 사용해야함.

 

3. 전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void BFS(vector<vector<int>>& grap, vector<bool>& visit, int st){
    queue<int>check;
    check.push(st); // queue 시작점

    while(!check.empty()){
        int next = check.front();
        check.pop();

        for(int x: grap[next]){ // 정점이랑 연결된 애들 탐색
            if(visit[x]){ // 연결된 정점이 방문한 애가 아니면
                cout << x << " "; // 출력하고 
                visit[x] = false; // 방문처리
                check.push(x);
            }
        }
    } // 연결된 애들 다 봤으면 처음 연결되어있던 정점이랑 연결된애들 보러 넘어가기
    return;
}

void DFS(vector<vector<int>>& grap, vector<bool>& visit, int st){
    visit[st] = true; // 정점 방문처리

    for(int x:grap[st]){ // 정점이랑 연결된 애들 탐색
        if(!visit[x]){ // 연결된 정점이 방문한 애가 아니면
            cout << x << " "; // 출력하고
            DFS(grap, visit, x); // dfs 돌면서 연결된 그 정점으로 넘어가기
        }
    }
    return;
}

int main(){
    int N, M, st_point, a, b;
    cin >> N >> M >> st_point;
    vector<vector<int>> grap(N+1);
    vector<bool> visit(N+1, false);

    grap[0]. push_back(st_point);
    while(M--){
        cin >> a >> b;
        grap[a].push_back(b);
        grap[b].push_back(a);
    } // 연결 입력받기

    // 여러개 연결시 작은거부터 방문 -> 정렬 필요
    for(int x = 1; x<grap.size(); ++x) sort(grap[x].begin(), grap[x].end());
   
    DFS(grap, visit, 0);
    cout << "\n";
    BFS(grap, visit, 0);

    return 0;
}

 

4. +@ DFS stack으로 실행하기

void DFS_stack(vector<vector<int>>& grap, vector<bool>& visit, int st) {
    stack<int>check;
    check.push(st);
    visit[st] = true; // 방문처리

    while (!check.empty()) {
        int next = check.top();
        check.pop();

        for (int i = grap[next].size() - 1; i >= 0; --i) {//뒤에서 부터 반복!!!!
            int n = grap[n][i];
            if (!visit[n]) {
                cout << n << " ";
                visit[n] = true;
                check.push(n);     // 현재 노드 다시 넣기
                check.push(n);    // 다음 노드 넣고 바로 거기로 이동
                break;           // 깊이 우선이므로 break
            }
        }
    }
}