18. 깊이 우선 탐색 (DFS algorithm)

  BFS와 더불어 탐색 알고리즘 중에서 많이 사용되는 것이 바로 '깊이 우선 탐색' 알고리즘이다. 너비 우선탐색이 Queue를 이용해 알고리즘을 구현했다면, DFS는 Stack을 이용해 구현하게 된다. 자신과 인접한 노드 하나를 선택하고, 해당 노드에 또 인접한 정점 하나를 계속 탐색하는 방식으로 탐색하게 된다. 쉽게 설명해 연결된 노드 끝까지 탐색하는 방식이다.

1. DFS Algorithm 방문 순서

  DFS 알고리즘에서는 시작 노드와 인접한 모든 노드를 Stack에 쌓게 된다. 위와 같은 그래프 구조에서 한번 탐색하는 순서를 살펴보자.

  시작 노드 1번에서 출발한다고 가정해보면 1번 노드와 인접한 2,3,4번 노드 중 가장 빠른 2번으로 이동하게 되고 Stack에 1번 노드와 인접한 노드인 2, 3, 4를 삽입한다.

STACK : (2, 3, 4) / 방문 순서 : 1

  그 다음 스택에서 가장 앞에 있는 값 하나를 반환해서 해당 노드와 인접한 노드를 탐색하게 된다. 위와 같은 경우 2번 노드를 탐색하게 되고 2번 노드와 인접한 노드들을 다시 스택에 삽입한다.

STACK : (3, 5, 3, 4) / 방문 순서 : 1-2

  스택에서 가장 앞에 있는 3번 노드에서 위와 같은 과정을 반복한다.

STACK : (4, 6, 7, 5, 3, 4) / 방문 순서 : 1-2-3

  그 다음 스택에 가장 앞에 있는 4번 노드에서도 같은 과정을 반복한다.

STACK : (8, 6, 7, 5, 3, 4) / 방문 순서 : 1-2-3-4

STACK : (7, 6, 7, 5, 3, 4) / 방문 순서 : 1-2-3-4-8

STACK : (6, 7, 5, 3, 4) / 방문 순서 : 1-2-3-4-8-7

STACK : (7, 5, 3, 4) / 방문 순서 : 1-2-3-4-8-7-6

이때, 7번 노드는 이미 방문을 한 노드이므로 건너 뛰고 그 다음 노드인 5번으로 이동하게 된다.

STACK : (3, 4) / 방문 순서 : 1-2-3-4-8-7-6-5

  이 과정을 통해 모든 탐색이 종료되게 된다.

2. DFS 구현

DFS 코딩으로 구현하게 되면 아래와 같이 나온다.

package dfs;
 
import java.util.*;
 
public class Solution {
 
    public static int size;
    public static int map[][];
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        
        // 입력 변수
        System.out.println("Size를 입력하시오:");
        size = sc.nextInt();
        
        map = new int [size][size];
        
        int a, b;
        System.out.println("간선을 입력하시오(종료 -1, -1):");
        
        while (true){
            a=sc.nextInt();
            b=sc.nextInt();
            if(a == -1 && b == -1) break;
            map[a][b]=1;
        }
        
        Dfs dfs = new Dfs(0,size,map);
        dfs.DfsAction();
    }
 
}
 
class Dfs{
    
    int start;
    int size;
    public static int[] token;
    public static int[][] map;
    
    Dfs(int a, int b, int[][] map){
        start = a;
        size = b;
        Dfs.map = map;
    }
    
    public void DfsAction(){
 
        // 방문 여부 저장
        token = new int[size];
        // start 정점 방문 표시
        token[start] = 1;
        // 큐 생성
        Stack<Integer> stack = new Stack<Integer>();
        // 시작 점 큐 입력
        stack.add(start);
        
        // Dfs 탐색 
        while(!stack.isEmpty()){
            // 큐에서 값 뺴오기
            int temp = stack.pop();
            System.out.println(temp);
            // 0~size 탐색
            for(int i = size-1; i>0 ;i--){
                // 길이 존재하고 방문하지 않았다면
                if(map[temp][i]==1 && token[i]==0){
                    // 큐에 추가
                    stack.add(i);
                    // 이동
                    token[temp]=1;
                }
            }
            
        }
        
    }
    
}
 

결과는 아래와 같이 나온다.

3. DFS 응용

  앞에서 풀어보았던 미로 탐색 문제를 DFS를 이용해 풀어보도록하자.

  위 그림과 같은 미로가 존재할때, DFS를 활용하여 최단거리를 구할 수 있다. 

  DFS 알고리즘으로 문제를 해결하기 위해선 BFS와 달리 Stack을 사용해야 한다. Java에서는 Stack에 대한 라이브러리가 제공된다. 따라서, Stack 함수를 통해 조금 더 쉽게 DFS 알고리즘을 만들 수 있다.

Peek() : Stack에 가장 끝에 있는 객체를 반환하나, Stack에서 제거하지 않는다.

Pop() : Stack에 가장 끝에 있는 객체를 반환하고 Stack에서 제거한다.

이 두 함수를 잘 활용한다면 DFS 관련 문제를 쉽게 풀 수 있다.

package dfsproblem;
 
import java.util.*;
 
public class Solution {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        
        // mapsize 입력
        int size = sc.nextInt();
        
        // map 입력
        int[][] map = new int[size][size];
        Vertex[][] vertex = new Vertex[size][size]; 
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                // vertex 정의
                vertex[i][j]=new Vertex();
                vertex[i][j].x=i;    
                vertex[i][j].y=j;
            
            }
        }
        
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){        
                // map 생성
                map[i][j]=sc.nextInt();
                // 0인 경우 길이 없고, 1인 경우 길이 있다.
            }
        }
        
        //DFS를 위한 스택 생성
        Stack<Vertex> stack = new Stack<Vertex>();
        
        // Vertex 시작점 정의하기
        vertex[0][0].dist = 1;
        
        // 스택에 삽입
        stack.add(vertex[0][0]);
        
        while(!stack.isEmpty()){
            // 스택에 vertex가 없으면 종료
            if(stack.peek()==null){ 
                System.out.println("더이상 길이 없습니다.");
                break;
            }
            
            // Vertex에서 위치 가져오기
            int x = stack.peek().x;
            int y = stack.peek().y;
            int dist = stack.peek().dist;
            
            // 도착점에 도착하면 종료
            if(x==size-1 && y==size-1){
                System.out.println("도착점입니다.");
                System.out.println("거리: "+dist);
                break;
            }
            
            // 방문 Vertex의 경우 넘어간다.
            if(stack.peek().visited==true){
                stack.pop();
                continue;
            }
            
            // 방문하지 않았다면, 방문처리 한 뒤 연산을 수행한다.
            else{
                stack.peek().visited=true;
            }
            
            // 탐색 후 큐에서 제거 함
            stack.pop();
            
            // 위쪽 탐색
            if(x!=0 && map[x-1][y]==1){
                vertex[x-1][y].dist = dist+1;
                stack.add(vertex[x-1][y]);
              }
            
            // 아래쪽 탐색
            if(x!=size-1 && map[x+1][y]==1){
                vertex[x+1][y].dist = dist+1;
                stack.add(vertex[x+1][y]);
            }
            // 좌측 탐색
            if(y!=0 && map[x][y-1]==1){
                vertex[x][y-1].dist = dist+1;
                stack.add(vertex[x][y-1]);
            }
            
            // 우측 탐색
            if(y!=size-1 && map[x][y+1]==1){
                vertex[x][y+1].dist = dist+1;
                stack.add(vertex[x][y+1]);
            }
            
        }
        
    }
 
}
 
class Vertex{
    //초기 인덱스 
    int x=-1; int y=-1;
    //연결 Vertex
    LinkedList<Vertex> linkedList=new LinkedList<Vertex>();
    int dist=-1;
     
    boolean visited=false;
}