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

 

 

 

[ 특징 ] 

그래프 완전 탐색 기법으로 모든 노드를 검색한다.

시작노드에서 탐색할 쪽의 분기를 정해 최대깊이까지 탐색 후 다른 쪽 분기로 이동해 다시 탐색 = 넓게 탐색 전 깊이 탐색

재귀함수 or 스택을 이용하여 구현 - 순환 알고리즘의 형태

 

 

[ 시간복잡도 ] 

인접리스트로 표현된 경우 O(V+E) [ V : 노드 수 , E : 에지 수 ] 

인접행렬로 표현된 경우 O(N^2)

 

 

장점 : 단지 현 경로상의 노드만을 기억하면 되므로 저장공간의 수요가 비교적 적다.

        : 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점 : 단순 검색 속도는 BFS에 비하면 느리다.

        : 얻어진 해가 최단 경로가 된다는 보장이 없다.

          이는 목표에 이르는 경로가 다수인 문제에 대해 DFS는 해에 다다르면 탐색을 끝내버리므로,

          이때 얻어진 해는 최적이 아닐 수도 있다.

 

 

[ 구현시 고려해야 하는 점 ]

한 번 방문한 노드에 다시 방문하지 않는다

 -> 방문 여부를 체크할 배열이 필요하며 체크하지 않을 경우 순환 알고리즘의 형태기에 무한루프에 빠질 위험이 있다.

 

 

 

---

 

 

[ 스택으로 알아보는 탐색 순서 ]

예를 들어 아래의 원본 그래프(유향그래프)가 있을 경우 다음과 같이 인접리스트를 그린다.

또한 방문 체크 배열을 만들어 각 노드들이 재방문되는 것을 방지한다.

 

 

탐색 순서를 보면 일단 시작노드를 1로 잡고 1을 push 하고 pop 한다. ( 이때 1의 방문체크배열 값을 true로 변경한다. )

1을 pop 하면서 1과 연결된 2와 3을 push 한다. ( 2,3의 방문체크배열값을 true로 변경한다. )

3을 pop 하면서 3과 연결된 4를 push 한다. ( 4의 방문체크배열값을 true로 변경한다. )

4를 pop하면서 4와 연결된 6을 push 한다.  ( 6의 방문체크배열값을 true로 변경한다. )

6을 pop 한다. 6은 연결된 노드가 없기에 push하지않는다.

2를 pop 한다. 2와 연결된 5를 push한다. ( 5의 방문체크배열값을 true로 변경한다. )

5를 pop한다. 5는 연결된 노드가 없기에 push 하지 않는다.

 

탐색순서 : 1 - 3 - 4- 6 - 2 - 5 ( pop한 순서 )

 

 

 

---

 

 

 

[ DFS 구현 코드 - 재귀 ] 

import java.util.ArrayList;
import java.util.Scanner;

public class DFSMYHAVEDIR {
    // 데이터를 넣을 배열
    private ArrayList<Integer>[] ll;
    // 방문 여부를 체크할 배열
    private boolean visited[];
    // 노드 수
    private int node;

	// 배열 초기화
    DFSMYHAVEDIR(int node) {
        this.node = node;
        ll = new ArrayList[this.node + 1];
        visited = new boolean[this.node + 1];
        for (int i = 1; i < node + 1; i++) {
            ll[i] = new ArrayList<Integer>();
        }
    }

	// 엣지 추가 
    void addEdge(int index, int data) {
        ll[index].add(data);
    }

    // 시작노드가 있는 경우
    void DFS(int startnode) {
        System.out.print("탐색순서: ");
        // 설정한 노드를 가지고 탐색 함수 실행
        DFSUtil(startnode);
        System.out.println();
    }

    // 시작노드가 없는 경우
    void DFS() {
        System.out.print("탐색 순서: ");
        // 시작 노드가 없는 경우 1번 노드를 시작노드로 하여 탐색 함수 실행
        for (int testNode = 1; testNode < node + 1; testNode++) {
            if (!visited[testNode]) {
                DFSUtil(testNode);
            }
        }
        System.out.println();
    }

    void DFSUtil(int testNode) {
    	// 탐색할 노드가 방문한 적 없는 노드 일 경우 노드를 출력하고 그 노드를 기준으로 다시 탐색시킴
        if (!visited[testNode]) {
            System.out.print(testNode + " ");
            visited[testNode] = true;
            for (int i : ll[testNode]) {
                if (!visited[i]) {
                    DFSUtil(i);
                }
            }
        }
    }

	// 배열 출력
    void printfArray() {
        System.out.println("-------------------");
        for (int i = 1; i < node + 1; i++) {
            System.out.print("arraylist[" + i + "] : ");
            for (int k : ll[i]) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
    }

	// 시작노드를 1로 설정했기에 둘 다 같은 경로가 나와야한다.
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        DFSMYHAVEDIR myDfs = new DFSMYHAVEDIR(9);
        DFSMYHAVEDIR myDfs2 = new DFSMYHAVEDIR(9);
        myDfs.addEdge(1, 2);
        myDfs.addEdge(1, 3);
        myDfs.addEdge(1, 4);
        myDfs.addEdge(2, 5);
        myDfs.addEdge(2, 6);
        myDfs.addEdge(5, 7);
        myDfs.addEdge(3, 8);
        myDfs.addEdge(4, 8);
        myDfs.addEdge(4, 9);
        myDfs.addEdge(7, 3);
        myDfs.printfArray();
        myDfs.DFS(1);
        myDfs2.addEdge(1, 2);
        myDfs2.addEdge(1, 3);
        myDfs2.addEdge(1, 4);
        myDfs2.addEdge(2, 5);
        myDfs2.addEdge(2, 6);
        myDfs2.addEdge(5, 7);
        myDfs2.addEdge(3, 8);
        myDfs2.addEdge(4, 8);
        myDfs2.addEdge(4, 9);
        myDfs2.addEdge(7, 3);
        myDfs2.printfArray();
        myDfs2.DFS();
        sc.close();
    }
}

 

 

 

 

 

현재는 유향그래프이지만 만약 방향이 없는 그래프일 경우 엣지 추가 시 addEdge(1,2)와 addEdge(2,1)처럼 짝을 이뤄 추가해 주거나

아래와 같이 addEdge 함수를 변경해 주면 된다.

( 물론 이 경우엔 index, data로 매개변수를 사용하는 것보단 node1, node2로 이름을 지어주면 좋지 않을까 싶다.)

void addEdge(int index, int data) {
        ll[index].add(data);
        ll[data].add(index);
}

  

 

 

---

 

 

 

 

[ DFS 구현 코드 - 스택 ]

 

import java.io.*;
import java.util.*;

class Main {
  static boolean visited[] = new boolean[9];
  static int[][] graph = { {}, { 2, 3, 8 }, { 1, 6, 8 }, { 1, 5 }, { 5, 7 }, { 3, 4, 7 }, { 2 }, { 4, 5 }, { 1, 2 } };

  static void dfsStack(int start) {
  	// 스택생성
    Stack<Integer> st = new Stack<Integer>();
    
    // 시작노드 출력 및 스택 삽입
    System.out.print(start + " ");
    st.push(start);
    visited[start] = true;
    
    // 빈스택이 될 때까지 반복
    while (!st.isEmpty()) {
      int node = st.pop();
      for (int i : graph[node]) {
      // 방문하지 않은 노드일 경우 스택에 삽입 + 방문배열 값 true로 변경 + 출력
        if (!visited[i]) {
          visited[i] = true;
          System.out.print(i + " ");
          st.push(i);
        }
      }
    }

  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    //시작 노드 입력받기
    int start = sc.nextInt();
    dfsStack(start);
  }
}

 

 

 

---

 

 

 

 

[ 참고문헌 ]

인프런 Do it! 알고리즘 코딩테스트 with JAVA

https://www.inflearn.com/course/lecture?courseSlug=두잇-알고리즘-코딩테스트-자바&unitId=148282&tab=curriculum

블로그

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://better-tomorrow.tistory.com/entry/DFS-BFS-이해하기