[JAVA] DFS 깊이 우선 탐색

 

DFS 깊이 우선 탐색

: DFS(Depth First Search)는 하나의 정점으로부터 시작하여 깊은 곳 우선으로 탐색하여, 더 이상 갈 곳이 없을 경우 이전 단계로 되돌아가 다른 경로를 탐색해 최종적으로는 연결된 모든 정점을 탐색하는 방법이다.

 

 

📍 DFS 특징

• 재귀적 또는 스택을 이용해 구현한다.
• 각 정점의 방문 여부를 확인하기 위해 방문 배열을 사용한다. (예. int[] visited)
• 그래프가 순환 구조를 가질 경우, 무한 루프 방지를 위해 반드시 방문 여부를 체크해야 한다.

 

📍 DFS 시간 복잡도

• 인접 리스트 사용 시 : O(V+E) → V: 노드 수/ E: 간선 수
• 인접 행렬 사용 시 : O(V^2)

 

📍 DFS 동작 알고리즘

1. 시작 노드를 방문하고 방문 여부를 체크한다.

2. 해당 노드와 연결된 인접 노드 중 방문하지 않은 노드를 탐색한다.

3. 더 이상 방문할 노드가 없으면 이전 노드로 되돌아간다.

4. 모든 노드를 방문할 때까지 반복한다.

 

 

📍 DFS 코드 구현해보기

 

✔️ 재귀

public class Main{
    static Stack<Integer> stack = new Stack<>();
    static StringBuilder sb = new StringBuilder();
    static boolean node[][] = new boolean[n+1][n+1], visited[] = new boolean[n+1];
    
    static void dfs(int v) {
        if(visited[v])
            return;
        sb.append(v+" ");
        for(int i=1; i<=n; i++)
            if(node[v][i] && !visited[i]) {
                visited[i] = true;
                dfs(i);
            }
    }
    
}

 

✔️ 스택 사용

public static String dfs(int v, boolean node[][]) {
    StringBuilder sb = new StringBuilder();
    Stack<Integer> stack = new Stack<>();
    boolean visited[] = new boolean[n+1];
    
    stack.add(v);
    int idx;
    
    while(!stack.isEmpty()) {
        idx = stack.pop();
        
        if(visited[idx])
            continue;
        visited[idx] = true;
        
        sb.append(idx+" ");
        
        for(int i=0; i<n; i++)
            if(node[idx][i] && !visited[i])
                stack.add(i);
    }
    return sb.toString();
}

 

 

📍DFS 사용 예시

• 전위 순회
• 미로 탐색
• 그래프 연결요소 찾기