[알고리즘] DFS 깊이 우선 탐색

DFS란?

그래프의 가장 깊은 부분을 우선적으로 탐색하는 알고리즘. 아래로 우선 내려감.
인접 행렬과 인접 리스트로 표현 가능.

 

• 인접 행렬: 2차원 배열로 그래프의 연결 관계 표헌.
• 인접 리스트: 리스트로 그래프의 연결 관계 표현.

메모리 측면에서 인접 행렬은 모든 관계를 저장하기 때문에 메모리 낭비가 많음.
속도 측면에서 특정 노드의 정보를 얻을 때 인접 리스트는 모든 관계를 확인해야하기 때문에 느림.

 

DFS는 최대한 깊이 들어간 후 다시 돌아 오면서 탐색하는 방법을 사용하기 때문에 Stack 사용.

DFS 방법

1. 시작 노드를 스택에 삽입하고 방문 처리.
2. 스택 최상단 노드에 방문하지 않은 인접 노드를 스택에 push 후 방문 처리. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드 pop.(인접 노드 중 방문 번호가 낮은 순서대로 처리)
3. 2번을 처리할 수 없을 때 까지 실행.

스택을 이용하기 때문에 재귀로도 구현 가능.

 

구현

public class DFS {

    public static void dfs(int[][] graph, int n, boolean[] visited) {
        visited[n] = true;
        System.out.println(n);
        for (int i = 0; i < graph[n].length; i++) {
            int now = graph[n][i];
            if (!visited[now]) {
                dfs(graph, now, visited);
            }
        }
    }

    public static void Solution(int[][] graph) {
        boolean[] visited = new boolean[graph.length];
        dfs(graph, 1, visited);
    }

    public static void main(String[] args) {
        int[][] graph = {{},
                {2, 3, 8}, // 1번 노드와 연결된 노드들
                {1, 7}, // 2번 노드와 연결된 노드들
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}};
        Solution(graph);
    }
    
}