깊이 우선 탐색(DFS)

◼︎ DFS: 깊이 우선 탐색(Deep First Search)

• 그래프의 모든 노드를 방문하고자 하는 경우에 사용하는 알고리즘
• 시작 노드에서 시작해, 다음 분기(branch)로 넘어가기 전, 해당 분기를 모두 탐색하는 방식
• 스택 or 재귀 함수를 통해 구현

---

► DFS 시간 복잡도

V: 노드 수, E: 간선

인접행렬 : O(V^2)
인접 리스트 : O(V+E)

왜 이런 시간 복잡도가 나타나는지

인접행렬을 사용하는 경우, 모든 노드와 간선의 관계를 확인해야 하기 때문에 V^2의 시간 복잡도를 가진다. 인접행렬은 모든 노드 간의 연결 상태를 행렬로 표현하며, 이를 위해 모든 노드 쌍을 확인해야 한다.

인접리스트를 사용하는 경우, 각 노드에 대해 연결된 모든 간선을 확인해야 한다. 각 노드를 한 번씩 방문하므로 시간 복잡도는 O(V)이고, 각 노드에서 연결된 모든 간선을 확인해야 하므로 추가로 O(E)의 시간이 필요하다. 그래서 인접 리스트의 경우 시간 복잡도는 O(V+E)가 된다.

어떤 상황에서 인접 행렬, 리스트를 사용해야 할까

인접 행렬은 모든 노드의 연결 상태를 한 번에 확인할 수 있지만, 그래프가 크고 간선이 적은 희소 그래프(Sparse Graph)의 경우, 불필요한 공간을 많이 차지하게 되며, 시간 복잡도가 O(V^2)로 높다.

반면, 인접 리스트는 간선의 정보만을 저장하므로, 공간 효율성이 높다. 또한, 각 노드에 연결된 간선만 확인하면 되므로 작업이 빠르며, 시간 복잡도가 O(V+E)로, 간선의 수가 적은 희소 그래프에서는 훨씬 효율적이다.

즉

• 간선 수가 많은 밀집 그래프(Dense Graph)에서는 인접 행렬
• 간선 수가 적은 희소 그래프에서는 인접 리스트

---

► DFS Snippets Java

DFS 인접 행렬 구현

백준 바이러스 문제를 DFS 재귀 함수로 풀었던 것 기록

        //노드 수 (컴퓨터)
        int n = sc.nextInt();
        //엣지 수
        int edge = sc.nextInt();

        // 엣지를 기준으로 인접 행렬 할당
        matrix = new int[n + 1][n + 1];
        for (int i = 1; i <= edge; i++) {
            int v1, v2;
            v1 = sc.nextInt();
            v2 = sc.nextInt();
            matrix[v1][v2] = 1;
            matrix[v2][v1] = 1;
        }

노드 수와 엣지를 입력받고, 이를 기준으로 인접 행렬 생성

    // DFS 인접행렬 재귀 구현
    private static int dfs(int Node) {
        // 방문 체크
        visited[Node] = true;
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[Node][i] == 1 && !visited[i]) {
                count++;
                dfs(i);
            }
        }
        if (count == 0) {
            return 0;
        }
        return count;
    }

• 메인 메소드에서 시작 노드로 DFS를 호출
• 방문 체크를 한 후, 해당 노드에 연결 된 모든 노드들을 확인하며 아직 방문하지 않은 노드가 있으면 그 노드로 들어가 재귀적으로 DFS 수행하며, 연결된 && 방문하지 않은 모든 노드들을 방문하게 된다.

---