[バックアップ]1260 DFSとBFS C+(BFS/DFS)

📌バックアップ1260 DFSとBFS
https://www.acmicpc.net/problem/1260

BFSとDFSの問題が発生したのは初めてです.他のブログを参考に回答します.
BFSはキュー[優先FIFO]
DFSは再帰+ルートディレクトリ(フルナビゲーション)[後入先出LIFO]
使用方法.
DFSはスタックを用いた後入先出方式である.システムスタックを再帰的に使用します.
グラフィック表現には隣接マトリクスと隣接リストがあります.
隣接行列は2次元配列(行列)形式,隣接リストはベクトル配列形式である.
空間的複雑度は隣接行列O(V^2)、隣接リストO(V+E)である.
時間複雑度は,各ノードが接続されたすべてのノードをブラウズする際の隣接行列O(V),隣接リストO(E)である.
隣接テーブルは隣接マトリクスよりも空間的複雑度が小さく,探索時間も比較的速いため,隣接テーブルがよく用いられる.
ここでは隣接行列を用いた.

は、まず、DFS、BFSを実行するためにグラフィック(隣接マトリクス)およびアクセスレコードを必要とする.

全局は

隣接行列、アクセス記録、ノード数、幹線数を発表した.

戦区への進出が発表されれば、自動的に0に初期化される.

main()ノード、幹線数、および始点を入力します.
隣接する行列に入力された2つのノードが出会う場所に1を入れる.(1=接続)

DFSを実行し、順次出力します.

memsetを使用して初期化します.memsetの使用

BFSを実行し、順次出力、

を終了する.
1. DFS
アクセス履歴に追加の接続された要素があり、アクセス履歴がない場合は、DFSを実行して繰り返します.(在貴)
2. BFS
アクセスレコードを読み込み、キューを生成します.現在のノードをキューにプッシュします.
キューの前のノードをコピーし、キューから削除します.他のノードがコピーされたノードに接続されます.では、それらのノードをキューに入れます.順番は大丈夫です.それらのノードもアクセスレコードに残ります.Qが許しを請うまでこれを繰り返す.
DFSの方がBFSより簡単な感じQをたくさん使ったことがないので均一に使って焼いています

コード#コード#

#include <iostream>
#include <queue>    //BFS에서 활용
#include <string.h> //memset 쓰려면 필요
using namespace std;

/* 전역으로 정의 - 자동 0 초기화 */
int arr[1001][1001]; //인접행렬
int visited[1001];   //방문기록
int N, M, V;

/* DFS - 재귀(시스템 스택 사용) (후입선출 LIFO) */
void DFS(int V)
{
    visited[V] = 1;   //시작점 방문기록
    cout << V << " "; //방문한 노드 출력

    for (int i = 1; i <= N; i++)
    {
        if (arr[V][i] == 1 && visited[i] == 0)
        {
            DFS(i); //스택에 i 넣는 셈
        }
        if (i == N)
            return;
    }
}

/* BFS - 큐 사용 (선입선출 FIFO) */
void BFS(int V)
{
    queue<int> q; //큐 생성
    q.push(V);    //시작노드 큐에 넣음

    while (!q.empty())
    {
        int next = q.front(); //큐 맨 앞에 값을 방문
        visited[next] = 1;    //방문기록
        cout << next << " ";  //방문한 노드 출력
        q.pop();              //큐에서 뺌

        //방문했던 노드와 가까운 노드 큐에 넣어줌
        for (int i = 1; i <= N; i++)
        {
            if (arr[next][i] == 1 && visited[i] == 0)
            {
                q.push(i);         //큐에 넣어줌
                visited[i] = 1; // i 점은 미리 방문기록 - 안하면 중복으로 방문할 수도 있다
            }
        }
    }
    
}

int main()
{
    int u, v;
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        arr[u][v] = 1;
        arr[v][u] = 1; //자리바꿔서도 해주는 이유 : 무방향이기 때문
    }                  //입력 즉시 인접행렬에 넣어줌, 다 돌면 인접행렬 완성

    DFS(V); // DFS 수행

    cout << "\n";                        //개행
    memset(visited, 0, sizeof(visited)); //방문기록 visited 초기화

    BFS(V); // BFS 수행
}

📌リファレンス
https://velog.io/@leobit/%EB%B3%B5%EC%9E%A1%EB%8F%84Complexity