깊이 우선 탐색(Depth First Search)

DFS란 말 그대로 깊이를 우선적으로 탐색하는 방법이다. 좀 더 쉽게 말하면, 갈림길(분기점)이 있다면 한방향으로 끝까지 간 후에 답을 확인하는 과정을 반복한다. 따라서 재귀함수를 기본적으로 이해를 해야한다.

코드

#include<bits/stdc++.h>
using namespace std;
const int n = 6;
vector<int> adj[n];
int visited[n];
void dfs(int u){
    visited[u]= 1;
    cout << u << '\n';
    for(int v : adj[u]){
        if(visited[v] == 0){
            dfs(v);
        }
    }
    cout << u << "로부터 시작된 함수가 종료되었습니다.";
}

int main(){
		//간선 만들기
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    dfs(1);
    
    return 0;
}

코드를 보면 방문을 했으면 1, 방문을 하지 않았으면 0이다. u로부터 인접해 있는 간선들이 0이라면 dfs를 호출하여 재귀적으로 탐색한다. 재귀 함수는 LIFO(Last In, First Out) 원칙을 따른다. 즉, 가장 나중에 호출된 함수가 가장 먼저 종료된다. ex) f(1) → f(2) → f(3)으로 호출을 했다면 f(3) → f(2) → f(1) 순서로 종료가 된다. 재귀 함수가 호출될 때마다 호출된 함수가 스택(stack)에 쌓이는데, 나중에 쌓인 함수가 먼저 처리된다. 따라서 가장 처음 호출된 함수는 스택의 가장 아래에 쌓이게 되고, 가장 나중에 호출된 함수가 먼저 완료된 후, 그 다음 함수가 완료되며 순차적으로 스택에서 제거된다. 복습 차원겸 간만에 풀어보았는데 인접리스트부터 다시 dfs를 복습하려니 가물가물해서 시간이 오래걸렸다.

Reference

나의 뇌