DFS(깊이 우선 탐색)

학교 다닐때에도 배우지 못한 것은 애가 대학교에 다니면서 같이 배우게 된다.

(퍼온 곳 : [알고리즘] 그래프(Graph)의 탐색 – DFS(깊이 우선 탐색)

깊이우선탐색은 스택을 이용해서 갈 수 있는 만큼 최대한 많이 간 다음, 갈 수 없으면 이전의 정점으로 돌아가는 방식을 사용한다.  최단경로를 추척할 때 사용하기도 하지만 최적의 경로를 보장하지 않는다.

다른 검색 방식으로 넓이 우선 방식도 있다.

 

/*
n = 정점 개수
m = 간선 갯수
start = 시작 번호

u, v = 점 u와 점 v가 이어진다.

ex) 6 7 1
1 2
1 5
2 3
2 5
3 4
4 5
4 6
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

vector<int> a[1001];
bool check[1001];

void dfs(int node)
{
    check[node] = true; // 현재 노드를 방문했다는 표시
    cout << node << " "; // 방문한 노드 출력

    // 노드 수 만큼
    for (int i = 0; i < a[node].size(); i++)
    {
        int next = a[node][i]; // 다음 방문할 노드를 저장

        if (check[next] == false) // 방문할 노드의 방문 표시가 없다면 탐색 ㄱㄱ
            dfs(next);
    }
}

void printValue(int m) {
    // 내용을 출력
    for (int i=0;i<m;i++) {
        for (int j=0;j<a[i].size();j++) {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m, start;
    cin >> n >> m >> start;

    // 그래프 입력
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        a[u].push_back(v);
        a[v].push_back(u);
    }

    // 입력한 간선 정렬
    for (int i = 1; i <= n; i++)
        sort(a[i].begin(), a[i].end());

    printValue(m);

    // 탐색하여 결과 출력하는 함수
    dfs(start);
    puts("");

    return 0;
}