(탐색알고리즘) 깊이 우선 탐색(DFS : Depth First Search)

깊이 우선 탐색(DFS : Depth First Search)

탐색 알고리즘에 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)이 있습니다.

이번 내용은 DFS를 주제로 포스팅하겠습니다!

DFS(깊이 우선 탐색)은 트리와 그래프 같은 자료구조에서 스택을 이용하여 데이터를 탐색할 때 사용되는 알고리즘입니다.

DFS 알고리즘 특징은 더이상 나아갈 길이 보이지 않을 만큼 깊이 찾아가면서 탐색합니다. 만약, 나아갈 길이 존재하지 않면 이전의 위치로 돌아와 찾아가지 않은 다른 길로 뻗어 나가면서 탐색해 나갑니다.

장점 

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

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

단점

해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 

얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

이미지 출처 : http://blog.eairship.kr/268

위의 그래프를 보면 각 정점(Vertex)가 있고 정점마다 간선(Edge)로 연결되어 있습니다. 1번 정점을 시작으로 방문을 한다고 가정하고 진행하겠습니다.

이미지 출처 : http://blog.eairship.kr/268

1. 현재 정점위치는 1번 정점이고 2번 3번 정점과 연결되어 있습니다, 두 정점 모두 방문하지 않았음으로 2번을 방문하였습니다.
   

2. 현재 정점위치는 2번 정점이고 1번 4번 5번 정점과 연결되어 있습니다. 1번 정점을 방문하였고 4번 5번 정점을 방문하지 않았음으로 4번을 방문하였습니다.

3. 현재 정점위치는 4번 정점이고 2번 8번 정점과 연결되어 있습니다. 2번 정점을 방문하였고 8번 정점을 방문하지 않았음으로 8번을 방문하였습니다.

4. 현재 정점위치는 8번 정점이고 4번 5번 6번 7번 정점과 연결되어 있습니다. 4번 정점을 방문하였고 5번 6번 7번 정점을 방문하지 않았음으로 5번을 방문하였습니다.

5. 현재 정점위치는 5번 정점이고 2번 8번 정점과 연결되어 있습니다. 2번 8번 정점 둘다 방문 했기 때문에 전에 방문한 정점으로 돌아갑니다.

6. 현재 정점위치는 8번 정점이고 4번 5번 6번 7번 정점과 연결되어 있습니다. 4번 5번 정점을 방문하였고 6번 7번 정점을 방문하지 않았음으로 6번을 방문하였습니다.

7. 현재 정점위치는 6번 정점이고 3번 8번 정점과 연결되어 있습니다. 8번 정점을 방문하였고 3번 정점을 방문하지 않았음으로 3번을 방문하였습니다.

8. 현재 정점위치는 3번 정점이고 1번 6번 7번 정점과 연결되어 있습니다. 1번 6번 정점을 방문하였고 7번 정점을 방문하지 않았음으로 7번을 방문하였습니다.

9. 현재 정점위치는 7번 정점이고 3번 8번과 연결되어 있습니다. 정점 3번 8번 모두 방문하였기 때문에 진행하지 않습니다.

진행과정중 5번과 6번이 이해가 잘 안갔습니다. 전 정점으로 돌아가 다음 6번 정점으로 진행을 한다. 어떻게 코드를 작성해야하나.. 고민했고, 스택과 재귀에 대해 이해하면서 고민을 풀 수 있었습니다. 아래에 위와 같은 그래프를 문제로 소스를 첨부하였습니다. 꼭 5번과 6번 진행과정에 대해 Debug를 하여 Logic 흐름을 파악하면 쉽게 이해가 갈 수 있을 것 입니다!

DFS를 구현하기 위해 정점사이의 관계를 나타내기 위해 인접 행렬을 사용하였습니다. 인접행렬에 대한 내용은 아래 정리하였습니다.

인접 행렬(Adjacency Matrix)

인접 행렬이란 정점과 정점 사이의 관계를 행렬로 표현한 것입니다. 

정점 A와 B가 연결되어 있다면 [A][B]는 1로 연결되어 있음을 알 수 있습니다. 그리고 [B][A]도 1로 연결되어 있음을 알 수 있습니다.

대각선 즉 [A][A], [B][B], [C][C], [D][D] 는 0이 되고 대각선을 기준으로 대칭이 됨을 알 수 있을 것입니다.

출처 : http://j1w2k3.tistory.com/585

깊이 우선 탐색 구현하기

첫 번째, 두 번째 이미지를 가지고 자바로 구현하였습니다.

public class DepthFirstSearch {
    static int vertex; //정점의 개수
    static int startVertex; //시작 정점
    static int[][] vertexMap; //인접 행렬 생
    static int[] vertexVisit; //정점의 방문 여부를 가리키는 배열
    static int vt1, vt2;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        vertex = scan.nextInt(); //정점의 개수 입력
        startVertex = Integer.parseInt(scan.nextLine().trim()); //시작할 정점입력
        vertexMap = new int[vertex+1][vertex+1]; //+1을 시킨 이후는 정점의 시작을 0이아닌 1로시작하기 위해서이다.!
        vertexVisit = new int[vertex+1]; //+1을 시킨 이후는 정점의 시작을 0이아닌 1로시작하기 위해서이다.!
        
        while(true) { 
            vt1 = scan.nextInt();
            vt2 = scan.nextInt();
        
            if(vt1 < 0 && vt2 < 0) //두 개의 점이 0보다 작을 경우 break;
                break;
            
            vertexMap[vt1][vt2] = vertexMap[vt2][vt1] = 1; 
        //정점 vt1과 vt2가 연결되었음을 표기
        //인접행렬의 내용을 이해하면 위에 코드를 이해할 수 있습니다. 
 //예를 들어 1정점 2정점이 연결되었으면 [1][2] 와 [2][1] 배열의 자리가 1이된다.
        }
        
        dfs(startVertex); //dfs를 시작합니다.
        
    }
    
    public static void dfs(int start) {
        vertexVisit[start] = 1;
        
        for(int i = 1; i <=vertex; i++) {
            if(vertexMap[start][i] == 1 && vertexVisit[i] == 0) {
                System.out.println(start + "->" + i + "로 이동합니다");
                dfs(i); 
            }
        }
    } 
}

DFS를 통한 최단 경로의 길이를 구하는 코드 작성하기.

아래의 S는 스타트점 F는 Finish점입니다. 회색점은 이동할 수 없고 흰색점으로만 이동할 수 있습니다.

출처 : http://j1w2k3.tistory.com/585

9번 부터 길이 나뉘어 집니다. 그렇게되면 최단거리를 13의 길이가 나올 수도 있고 돌아가게 되면 17의 길이가 나올 수 있게 됩니다. 

이 부분에서 유의해야 할 점은 재귀호출, 그리고 함수의 호출을 했을 때 순서를 잘 기억해야 된다는 것입니다. 함수 호출은 스택의 개념으로 생각하시면 됩니다.

import java.util.Scanner;

public class DFSExample {
    static int[][] map; //map을 나타내는 배열 
    static int[][] visited; 
    static int map_size; //map의 Size
    static int min;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        map_size = Integer.parseInt(scan.nextLine().trim()); //map의 size를 입력받는다.
        map = new int[map_size+1][map_size+1]; //map의 배열의 크기를 입력받은 map_size크기로 만든다.
        min = map_size * map_size;
        //이동할 수 있는 path를 입력받기 위해 for문을 사용.
        for(int i = 0; i < map_size; i++) {
            for(int j = 0; j < map_size; j++) {
                map[i][j] = scan.nextInt();
            }
        }
        
        depthfirstSearch(0,0,1);
        
        System.out.println("최단 거리 : " + min);
    }
    
    //dfs알고리즘 시작
    public static void depthfirstSearch(int x, int y, int length) {
        
        if(x == map_size -1 && y == map_size -1){
            if (min > length) min = length;
            return; 
        }
    
        map[y][x] = 0;
            
        //왼쪽으로 이동할 경우
        if(x > 0 && map[y][x-1] == 1) {
            depthfirstSearch(x-1, y, length+1);
        }
            
        //오른쪽으로 이동할 경우
        if(x < map_size && map[y][x+1] == 1) {
            depthfirstSearch(x+1, y, length+1);
        }
        //아래로 이동할 경우
        if(y < map_size && map[y+1][x] == 1) {
            depthfirstSearch(x, y+1, length+1);
        }
        //위로 이동할 경우
        if(y > 0 && map[y-1][x] == 1) {
            depthfirstSearch(x, y-1, length+1);
        }
        
        map[y][x] = 1;
    }
}