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

깊이우선탐색(DFS)이란?

• Depth First Search
• 그래프의 탐색방법중 한 가지로 시작한 노드에서 최대한 깊숙히(더 이상 갈곳이 없을때까지)탐색한 후 원점으로 돌아와서 다른 노드들을 탐색하는 방법입니다.

깊이우선탐색의 특징

• 자기 자신을 호출하는 순환 알고리즘
• 어떤 노드를 방문했는지를 반드시 체크해야한다. 
  체크하지 않으면 무한루프에 빠질 수 있다.

장점

• 구현이 간단하다.
• 현재 경로상의 노드만 기억하면 되므로 저장공간이 적게든다.
• 목표노드가 깊은곳에 있을경우에 빠르게 찾을 수 있다.

단점

• 단순 검색속도는 너비우선탐색보다 느리다.
• 해가 없는경우에 깊이 빠질 수 있다.
• 구한 경로가 최단경로가 아닐 수 있다.

실행순서 예시

구현 코드

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int arraySize = sc.nextInt();
        int commandSize = sc.nextInt();
        DFS dfs = new DFS(arraySize);

        for(int i=0; i< commandSize; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();

            dfs.array[start][end] = dfs.array[end][start] = 1;
        }

        dfs.dfs(0);
    }
}
class DFS{
    int array[][];
    int visit[];
    int size;

    public void dfs(int startIdx){
        visit[startIdx] = 1;
        System.out.println(startIdx + " 방문");
        for(int i =0; i<size; i++){
            if(array[startIdx][i] == 1 && visit[i] == 0){
                dfs(i);
            }
        }
    }
    public DFS(int size){
        this.array = new int[size][size];
        this.visit = new int[size];
        this.size = size;
    }
}