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

1. DFS(깊이 우선 탐색)?

DFS(Depth-First-Search)는 깊이 우선 탐색으로 스택 또는 재귀를 통해서 주로 구현이 됩니다. 

하나의 인접노드에 대해 모든 인접노드를 다 탐색한 뒤 다음 인접노드로 넘어가는 방식으로, 해당 노드에 대해 방문여부를 체크하는 것이 핵심입니다. 방문여부를 체크하지 않으면 무한루프에 빠질 위험이 있습니다.

 

예시로 사용될 그래프

---

2. 기본적인 원리

기본적인 동작 원리는 다음과 같습니다.

1. 현재 노드와 연결된 노드 중 하나의 노드 방문 여부 체크
2. 만약 이미 방문된 노드라면, 패스 / 만약 아직 방문되지 않은 노드라면, 방문
3. 현재 노드를 새로 방문한 노드로 변경
4. 인접노드가 없을 때까지 1~3번 반복
5. 더 이상 갈 수 있는 인접 노드가 없을 경우, 가장 최근의 분기점으로 되돌아가 다른 노드 방문

 

시작노드에게는 두 개의 인접 노드가 있습니다.

그 중 노드 번호가 더 빠른 1번 노드에 대해 먼저 방문여부를 체크하는데, 1번 노드는 아직 방문이 되지 않은 상태이므로 방문하게 됩니다. 이제 현재 노드는 1번 노드로 바뀌었으므로, 1번 노드의 인접노드들에 대해서 DFS 탐색이 재개됩니다. 2번 노드는 나중에 1번 노드의 인접 노드들이 더 이상 방문할 노드가 없을 때 방문하게 될 것입니다.

모든 과정을 그림으로 표시해 보겠습니다.

 

 

 

---

3. 정리

• 현재 탐색중인 경로만 기억합니다. 따라서 메모리 사용량 감소합니다.
• 구현은 주로 재귀를 사용하므로 비교적 간단한 편입니다.
• 단순 경로 검색 속도는 BFS보다 느립니다.
• 목표 노드에 도달할 경우 탐색이 종료됩니다. 따라서 중복된 경로에 대해 처리하지 못합니다. 이 말인 즉슨, 현재 경로가 최단경로인지에 대해 확인 불가능합니다. 따라서 최단 경로보다는 전체 탐색에 유리합니다.
• 백 트래킹(Back Tracking) 알고리즘에서 사용됩니다.

---

4. 간단한 코드 (Java)

public class DFS {

    static boolean[] visited = new boolean[6]; // 방문여부 저장 배열

    // 그래프 matrix로 표현
    static int[][] matrix = {{0,1,1,0,0,0},
                             {1,0,0,1,1,0},
                             {1,0,0,0,1,1},
                             {0,1,0,0,1,0},
                             {0,1,1,1,0,1},
                             {0,0,1,0,1,0}};

    public static void main(String[] args){ // main
        System.out.println("[0->5]에 대한 거리: "+dfs(0,5));
    }

    // DFS 탐색을 진행하는 함수
    static int dfs(int current_node, int target_node){
        if(current_node == target_node) // 현재 노드가 타겟 노드와 같으면
            return 1;

        for(int i = 0; i<6; i++){ // 반복문을 통해 방문되지 않은 인접노드 찾아서 방문(dfs)
            if(matrix[current_node][i] == 1 && !visited[i]){
                visited[i] = true;
                return dfs(i, target_node) + 1;
            }
        }
        return 0;
    }

}