[알고리즘] DFS 알고리즘 분석

개요

코딩테스트 문제를 푸는데 완전탐색을 해야하는 문제에 DFS를 사용하곤 한다.
DFS를 알고 있으면 문제를 전부 쉽게 풀 수 있을 줄 알았지만 문제마다 DFS를 약간 변형해서 풀어야 하기 때문에 처음에 시간을 조금 잡아먹었다.

그래서 문제 유형 별로 DFS 알고리즘을 정리해 보려고 한다.

그래프 완전 탐색

DFS 알고리즘을 푸는 데에 노드를 방문했는 지 체크하는 visit 컨테이너가 필요하다.
노드에 들어 있는 값을 인덱스로 삼아서 노드에 방문한다면 visit[x] = true와 같이 체크해주면 된다.
재귀호출 때 현재 노드에서 다음 값으로 설정된 값을 넘겨주는 것으로 다음 노드로 접근할 수 있다.

void dfs(int x)
{
    visited[x] = true;

    for (int i = 0; i < graph[x].size(); i++)
    {
        int y = graph[x][i];
        if (!visited[y])
            dfs(y); // 재귀적으로 방문
    }
}

조합 완전 탐색

접근 순서 자체를 그래프로 만들 기에는 조금 어려움이 있다.
이 때 visit 컨테이너는 앞의 visit와는 조금 다르게 사용한다.
꼬리 노드에서는 컨테이너를 전부 접근했기 때문에
visit 내부 원소가 전부 true가 된다.
상위노드로 다시 보내기 위해 재귀호출 후에 visit[x] = false와 같이 작성한다.

void dfs(){
   for(int i = 0; i < N; i++){
        if (visit[i]) continue;
        
        visit[i] = true;
        dfs(); // 재귀적으로 방문
        visit[i] = false;
    }
}