# DFS(深度優先搜尋)
## 前言
讓我們回想一下BFS(廣度優先搜尋)的運作方式，是不是像淹水一樣，向外擴張，直到整張地圖都被造訪過
DFS也可以是造訪整張地圖的演算法，但方式不同
在介紹DFS之前，我們要先了解「**遞迴**」的概念
## 遞迴
遞迴是一種將複雜問題分解為更小、相似的子問題來解決的方法，在程式裡面通常搭配自訂函式完成，透過呼叫自身來解決一個問題，並依賴於一個或多個終止條件來避免無限呼叫造成程式錯誤
### 遞迴示例：費氏數列

#include <iostream>
using namespace std;

int num[2000];

int f(int x){ //計算費氏數列
    if(x < 2) return x; //避免無限呼叫
    
    num[x] = f(x-1) + f(x-2); //定義式
    return num[x];
}

int main(){
    num[0] = 0;
    num[1] = 1;
    int n; cin >> n;
    f(n);
    cout << num[n];
}

根據費氏數列定義：
* $F_0 = 0$
* $F_1 = 1$
* $F_n = F_{n-1} + F_{n-2}$ $(n \geq 2)$

因此我們可以將自訂函式`f`的變數`x`設為索引值，並利用此函數使陣列存取我們得出的數，最後再回傳該索引值的值，供後面計算使用

> [!Tip]
> $f(\ )$ 內簡單流程 $(n = 3)$ ||(source: trt4497)||

## DFS的運作方式與應用
DFS的運作方式與BFS比較起來，較為容易理解，因為DFS比較貼近人腦的思考方式

DFS是遍歷或搜尋樹(Tree)或圖(Graph)的演算法
運作時DFS會探到底，如果走到不能走了，再回到起點，繼續走別條路試試看。
>[!NOTE]DFS 演示圖
>||(Source：https://zh-yue.wikipedia.org/wiki/File:Depth-First-Search.gif)||
>

DFS也可以進行排列組合的解題，==本章先以此例為主，其他應用後面內容會陸續提到==

## 例題
:::success
### [Zerojudge- e446. 排列生成](https://zerojudge.tw/ShowProblem?problemid=e446)
>科普：排列強調<font color = "f000">順序</font>，定義為從一組（或多個）不同的物件中，按照特定的順序選取一部分或全部物件的方法數
>ex. $1\ 2\ 3$可排成：
>$\{1\ 2\ 3\}, \{1\ 3\ 2\}, \{2\ 1\ 3\}, \{2\ 3\ 1\}, \{3\ 1\ 2\}, \{3\ 2\ 1\}$（按字典序排列)

根據題目，我們只需要進行一次排列的計算，我們可以運用```for```迴圈來迭代每個數字，並且記錄每個位置當前的數字，再往下一個位置做一樣的動作，同時確認是否使用過，(遞迴)直到數量 = $n$，就印出該組合並```return```

>[!Important] 有關字典序
>```for```迴圈的特性是由小到大迭代每個數，因此不需考慮字典序問題，會自動符合
:::spoiler AC Code

#include <iostream>
using namespace std;

int n, num[20], used[20] = {0};

void dfs(int idx){
    if(idx == n){
        for(int i = 0; i < n; i++){
            cout << num[i] << ' ';
        }
        cout << "\n";
        return;
    }
    for(int i = 1; i <= n; i++){
        if(used[i]) continue;
        num[idx] = i;
        used[i] = 1;
        dfs(idx + 1);
        used[i] = 0;
    }
}
int main(){
    cin >> n;
    dfs(0);
}

:::
:::warning
### [Zerojudge- i646. 排列組合-排列](https://zerojudge.tw/ShowProblem?problemid=i646)
這題概念與上題相同，但排列對象改為字母，我們可以運用字元的$ASCII\ \ number$做出數字轉字元
只要做到這件事，做法即與上題相同，只要注意此題輸入方式即可
:::spoiler AC Code

#include <iostream>
using namespace std;

int n, num[20], used[20] = {0};

void dfs(int idx){
    if(idx == n){
        for(int i = 0; i < n; i++){
            cout << char(num[i] + 'a');
        }
        cout << "\n";
        return;
    }
    for(int i = 0; i < n; i++){
        if(used[i]) continue;
        num[idx] = i;
        used[i] = 1;
        dfs(idx + 1);
        used[i] = 0;
    }
}
int main(){
    while(cin >> n){
        if(n == 0) return 0;
        dfs(0);
    }
}

:::
:::warning
### [Zerojudge- i645. 排列組合-組合](https://zerojudge.tw/ShowProblem?problemid=i645)
>科普：組合只關心<font color = "f000">元素</font>，定義為從一個集合中取出若干元素，不考慮順序
>ex. $1\ 2\ 3$在長度$2$的情況下，可組成以下不重複組合：
>$\{1\ 2\},\ \{1\ 3\},\ \{2\ 3\}$（按字典序排列)

字元處理的部分與上題相同就不做說明
組合的處理，我們需要為`for`迴圈做出微調，要確保迭代的起始數字正確，舉個例子說明：

[1, ]
[1, 2] //起始為2
[1, 3]
[2, ]
[2, 3] //起始為3

根據上例，我們可以得出結論：||for迴圈起始數字為前一數+1||
因此在`dfs()`中需要多一個區域變數來表示此起始值給`for`迴圈
:::spoiler AC Code

#include <iostream>
using namespace std;

int n, m, num[20],;

void dfs(int idx, int start){
    if(idx == m){
        for(int i = 0; i < m; i++){
            cout << char(num[i] + 'a');
        }
        cout << "\n";
        return;
    }
    for(int i = start; i < n; i++){
        num[idx] = i;
        dfs(idx + 1, i + 1);
    }
}
int main(){
    while(cin >> n >> m){
        if(n == 0) return 0;
        dfs(0, 0);
    }
}

:::