DFS

갈 수 있는 데까지 깊이 들어갔다가 막히면 되돌아 나오는 그래프 탐색. 미로에서 한 방향으로 끝까지 가보고 막다른 길이면 갈림길로 돌아오는 방식이다.

재귀와 방문 배열

재귀로 쓰는 것이 가장 자연스럽다. 방문할 수 있는 곳이 있으면 그리로 들어가는 함수를 자기 자신을 부르는 식으로 짜면, 더 갈 곳이 없을 때 함수가 끝나면서 알아서 돌아 나온다. 재귀가 곧 스택이라 콜 스택이 되돌아갈 경로를 대신 기억해준다.

static void dfs(int cur) {
    visited[cur] = true;
    for (int next : graph[cur]) {
        if (!visited[next]) dfs(next);
    }
}

visited 배열이 반드시 필요하다. 없으면 이미 다녀온 곳을 다시 방문해서 같은 자리를 무한히 맴돌고, 그래프에 사이클이 있으면 프로그램이 끝나지 않는다.

복잡도는 O(V + E)다. 모든 정점을 한 번씩 방문하고 모든 간선을 한 번씩 따라가기 때문이다. 모든 경로를 훑어야 하는 문제, 사이클 찾기, 위상 정렬, 완전 탐색과 백트래킹이 전부 이 뼈대를 쓴다.

BFS와의 차이

복잡도는 같지만 실제로는 DFS가 미묘하게 느리다. 재귀 호출 자체의 비용 때문인데, 신경 쓸 정도의 차이는 아니다.

최단거리와 연결 요소

DFS로는 최단거리를 구할 수 없다. 먼저 도달했다고 해서 그게 가장 짧은 경로라는 보장이 없다.

연결 요소가 여럿이면 한 번 돌려서는 전부 방문하지 못한다. 방문하지 않은 정점마다 탐색을 새로 시작해야 하는데, 그 이유와 예는 그래프에 적어두었다.

관련

• BFS
• 그래프
• 스택

출처

• 코드트리 그래프 탐색 - DFS