[BFS/DFS] DFS와 BFS(1260)(C++)

 

1. 문제 개요

 

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

 

2. 입출력

 

 

3. 문제 풀이

 

깊이 우선 탐색 (Depth-First Search): 최대한 깊이 내려간 후, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

너비 우선 탐색 (BFS, Breadth-First Search): 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

DFS, BFS는 특징에 따라 사용에 적합한 문제 유형이 있다.

그래프의 모든 정점을 방문하는 것이 주요한 문제인 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없다.

경로의 특징을 저장해둬야하는 경우 DFS를 사용한다.

최단거리를 구해야하는 경우 BFS를 사용하는 것이 유리하다.

 

DFS 알고리즘의 경우에는 스택 또는 재귀함수를 이용해서 구할 수 있다.

나는 재귀함수를 이용하는 방법을 사용했다. 이차원 벡터에 간선 연결에 대한 정보를 저장하고 visited 배열에 방문 여부를 표시했다.

또한 방문 순서를 저장하기 위해 list 벡터에 index를 push 해줬다.

void DFS(int index) {
    visited1[index] = true;
    list1.push_back(index);
    for(int i=0;i<v[index].size();i++) {
        int next = v[index][i];
        if(!visited1[next])
            DFS(next);
    }
}

 

BFS의 경우에는 큐를 사용해서 구현할 수 있다.

큐(queue)는 FIFO 방식으로 데이터를 저장한다. BFS의 경우에도 DFS와 마찬가지로 이차원 벡터에 간선 연결에 대한 정보를 저장하고 visited 배열에 방문 여부를 표시했고 방문 순서를 저장하기 위해 list 벡터에 index를 push 해줬다.

void BFS(int index) {
    queue<int> q;
    q.push(index);
    visited2[index] = true;
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        list2.push_back(current);
        for(int i=0;i<v[current].size();i++) {
            int next = v[current][i];
            if(!visited2[next]) {
                visited2[next] = true;
                q.push(next);
            }
        }
    }
}

 

4. 전체 코드

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

using namespace std;

const int MAX = 10001;

bool visited1[1001];
bool visited2[1001];

vector<int> v[MAX];
vector<int> list1;
vector<int> list2;

void DFS(int index) {
    visited1[index] = true;
    list1.push_back(index);
    for(int i=0;i<v[index].size();i++) {
        int next = v[index][i];
        if(!visited1[next])
            DFS(next);
    }
}

void BFS(int index) {
    queue<int> q;
    q.push(index);
    visited2[index] = true;
    while(!q.empty()) {
        int current = q.front();
        q.pop();
        list2.push_back(current);
        for(int i=0;i<v[current].size();i++) {
            int next = v[current][i];
            if(!visited2[next]) {
                visited2[next] = true;
                q.push(next);
            }
        }
    }
}

int main (void) {
    int N, M, V; //정점의 개수, 간선의 개수, 시작 번호
    scanf("%d%d%d",&N,&M,&V);
    int temp1, temp2;
    
    for(int i=0;i<M;i++) {
        scanf("%d%d",&temp1,&temp2);
        v[temp1].push_back(temp2);
        v[temp2].push_back(temp1);
    }
    
    for(int i=1;i<=N;i++) sort(v[i].begin(), v[i].end());
    
    BFS(V);
    DFS(V);
    
    for(int i=0;i<list1.size();i++) printf("%d ",list1[i]);
    printf("\n");
    for(int i=0;i<list2.size();i++)  printf("%d ",list2[i]);
}