[백준 / BOJ] C++ 1260 DFS와 BFS

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

1260번: DFS와 BFS

풀이

DFS란?

- 깊이우선탐색(Depth First Search)으로, 방문할 수 있는 정점이 있을경우, 계속해서 탐색해 나가는 방법이다.

보통 스택이나 재귀함수를 이용하여 탐색한다.

 

BFS란?

- 너비우선탐색(Breadth First Search)으로 해당 노드층의 방문한 정점에서 방문해 나갈 수 있는 모든 정점을 모두 탐색하는 것을 의미한다.

보통 큐를 이용하여 탐색한다.

 

DFS

우선 DFS는 스택으로 구현하였다. 입력받은 시작 정점을 먼저 push 해준 후, 

방문하지 않은 정점인 경우 방문하고, 해당 배열에 방문했다고 나타내준다.

그리고 입력받은 정점의 갯수만큼 하나씩 감소시키며 탐색한다.

 

BFS

BFS는 흔히 큐로 구현한다. 입력받는 시작 정점을 큐에 삽입한 후, 정점을 방문했다는 기록을 배열에 남긴다.

큐가 빌 때까지, 방문할 수 있는 정점이 없을때 까지 반복한다.

현재 정점에서 방문할 수 있는 정점들 중에서 방문하지 않은 정점을 큐에 넣어준다.

 

 

Code

#include<iostream>
#include<queue>
#include<stack>

using namespace std;

int line[1001][1001];
int isVisit[1001];
int N, M, V;

queue<int> _q;
stack<int> _stack;
void DFS(int vertex_num)
{

    _stack.push(vertex_num);


    while (!_stack.empty())
    {
        vertex_num = _stack.top();

        _stack.pop();
        if (!isVisit[vertex_num])
            cout << vertex_num << ' ';
        isVisit[vertex_num] = true;
        for (int i = N; i > 0; i--) 
        {
            if (line[vertex_num][i] && !isVisit[i])
            {
                _stack.push(i);
            }
        }

    }

}

void BFS(int vertex_num) 
{

    _q.push(vertex_num);

    while (!_q.empty()) 
    {

        vertex_num = _q.front();

        _q.pop();

        cout << vertex_num << ' ';

        for (int i = 1; i <= N; i++) 
        {
            if (line[vertex_num][i] && !isVisit[i])
            {
                _q.push(i);
                isVisit[i] = true;
            }
        }
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> V;


    for (int i = 0; i < M; i++) 
    {
        int from, to;
        cin >> from >> to;
        line[from][to] = 1;
        line[to][from] = 1;
    }

    DFS(V);

    cout << '\n';

    fill_n(isVisit, 1001, 0);

    isVisit[V] = true;
    BFS(V);
    return 0;
}