DFS, BFS 알고리즘 (1)

DFS의 경우 스택, BFS의 경우 큐를 이용해서 이해하는게 편함

방문했다는 걸 표시하는 배열, 그래프 정보가 있는 배열이 필요

 

작은 순으로 방문을 한다는 기준

DFS

1. 시작 노드 스택에 삽입, 방문처리

2. 인접 노드중 가장 작은수 방문처리, 스택에 삽입

3. 2번 반복, 더 이상 방문 가능한 노드가 없을 시 스택 pop

4. 스택 top으로 이동, 3번 반복

(스택을 쓴다는걸 재귀로 이해해서 구현)

 

BFS

1. 시작 노드 큐에 삽입, 방문처리

2. 큐의 front를 pop, 인접 노드들 모두 큐에 삽입 후 방문처리

3. 2번 반복

 

백준 1260번

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

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

int checkDFS[1002];
int checkBFS[1002];

void DFS(vector< vector<int> > vertex, int v){
    checkDFS[v]= 1;
    cout << v << " ";
    for(int i = 0; i < vertex[v].size(); i++){
        int next = vertex[v][i];
        if(checkDFS[next] == 0){
            DFS(vertex, next);
        }
    }
}

void BFS(vector< vector<int> > vertex, int v){
    checkBFS[v] = 1;
    queue<int> bfs;
    bfs.push(v);
    while(!bfs.empty()){
        int nowV = bfs.front();
        cout << nowV << " ";
        bfs.pop();
        for(int i = 0; i < vertex[nowV].size(); i++){
            if(checkBFS[vertex[nowV][i]] == 0){
                bfs.push(vertex[nowV][i]);
                checkBFS[vertex[nowV][i]] = 1;
            }
        }
    }
}
int main() {
    int N, M, start;
    cin >> N >> M >> start;
    vector< vector<int> > vertex(N + 1);
    for(int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }
    
    for(int i = 1; i < vertex.size(); i++){
        sort(vertex[i].begin(), vertex[i].end());
        
    }
    DFS(vertex, start);
    cout << endl;
    BFS(vertex, start);   
}