[ 백준 1260 ] DFS와 BFS (C++)

백준의 DFS와BFS(1260) 문제입니다.

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

[ 문제설명 ]

- 정점의 갯수와 간선의 갯수 그리고 탐색을 시작할 정점의 번호가 주어지고 서로 연결된 정점을 입력으로 받습니다.

- 입력을 통해서 하나의 그래프를 만들 수 있으며, 서로 연결된 정점은 양방향으로 연결되어 있습니다.

- 입력으로 주어진 탐색을 시작할 정점에서 탐색을 시작하는데, 출력결과를 DFS로 했을 때의 탐색 순서,

   BFS로 했을 때의 탐색 순서를 출력하면 됩니다.

[ 풀이과정 ]

1. 주어진 입력을 통해서 그래프를 만들어 봅니다.

   1-1) 서로 연결된 정점을 입력 받을 때, 양방향으로 연결되어 있으므로

         MAP[a][b] = MAP[b][a] = 1 이라는 과정을 해줘야 합니다.

2. DFS(Depth First Search)는 '넓게' 아닌 '깊게' 탐색하는 방식입니다. 스택(재귀)을 이용해서 구현하는 방식이며,

   가장 깊은 곳 까지 탐색 하고, 더 이상 들어갈 곳이 없으면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시

   탐색을 하는 방식입니다.

3. BFS(Breadth First Search)는 '깊게' 아닌 '넓게' 탐색하는 방식입니다. 깊은 곳으로 가기 전, 가장 가까운 정점부터

   탐색하는 방식으로, Queue를 사용해서 구현하는 방식입니다. 

4. BFS , DFS 모두 주의해야 할 점이 이미 한번이라도 방문을 했던 정점에 대해서는 다시 방문 하는 것을 방지할 수 있는

   무언가가 필요합니다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
int N, M, V;
int MAP[MAX][MAX];
bool Visit[MAX];
 
void Input()
{
    cin >> N >> M >> V;
    for (int i = 0; i < M; i++)
    {
        int Start, End;
        cin >> Start >> End;
        MAP[Start][End] = 1;
        MAP[End][Start] = 1;
    }
}
 
void DFS(int x)
{
    Visit[x] = true;
    cout << x << " ";
    for (int i = 1; i <= N; i++)
    {
        if (MAP[x][i] == 1 && Visit[i] == false) DFS(i);
    }
}
 
void BFS()
{
    queue<int> Q;
    Q.push(V);
    Visit[V] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front();
        Q.pop();
 
        cout << x << " ";
        for (int i = 1; i <= N; i++)
        {
            if (MAP[x][i] == 1 && Visit[i] == false)
            {
                Q.push(i);
                Visit[i] = true;
            }
        }
    }
}
 
void Solution()
{
    DFS(V);
    memset(Visit, false, sizeof(Visit));
    cout << endl;
    BFS();
}
 
void Solve()
{
    Input();
    Solution();
    cout << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}