[코테/알고리즘] 탐색 알고리즘 - DFS와 백트래킹

깊이 우선 탐색이란

루트 노드 (혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

넓게 탐색하기 전에, 깊게 탐색하는것이다.

더 이상 갈곳이 없는 정점에 도착했다면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 

 

•  깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.
•  검색 속도는 너비 우선 탐색보다 느리다.

 

DFS의 가장 큰 특징 ➡️  재귀적인 특징으로 구현을 한다.

그래서 각 원소를 포함시킬지 말지 여부를 다 시도해야 하는 완전 탐색의 경우 재귀호출이나 DFS로 짜는것이 쉽다.

 

다음은 그래프 형식의 DFS 이다.

노드 간 연결을 리스트로 관리한다.

import java.util.LinkedList;

public class DFS_study {

    static class Graph{
        // 전체 정점 개수
        private int V;
        // 연결리스트를 통한 간선
        private LinkedList<Integer> adj[];
        // 방문 여부 체크 배열
        private boolean[] visited;

        Graph(int v){
            V = v;
            adj = new LinkedList[v+1];
            for(int i=1; i<=v; i++){
                adj[i] = new LinkedList<>();
            }
        }

        //양방향 간선으로 연결
        void addEdge(int v, int w){
            adj[v].add(w);
            adj[w].add(v);
        }

        void DFS(int nodeIndex){
            //현재 노드를 방문 처리 한다. 
            visited[nodeIndex] = true;
            
            //방문한 노드를 출력한다.
            System.out.println(nodeIndex+" ");
            
            //현재 노드와 인접한 모든 노드 탐색
            for (int neighbor : adj[nodeIndex]){
                if (!visited[neighbor]){
                    DFS(neighbor);
                }
            }
        }
    }
}

 

 

 

 

다음으로는 2차원 배열(맵) 기반의 DFS이다.

행x열 개수로 자연스럽게 정점 개수가 결정되며, dx[], dy[] 방향 배열로 탐색한다.

간단한 미로 찾기 문제이다.

 

(예시 문제)
N×N 크기의 미로가 있다. 미로는 0과 1로 이루어져 있으며,
1은 이동할 수 있는 길, 0은 벽을 의미한다.
시작점은 항상 왼쪽 위 (0, 0)이고, 도착점은 오른쪽 아래 (N-1, N-1)이다.
현재 위치에서 상, 하, 좌, 우로만 이동할 수 있다.

1️⃣ (0,0)부터 출발해서 이동 가능한 모든 칸을 탐색하라.
2️⃣ 이동 가능한 칸을 방문 순서대로 출력하라.
3️⃣ 도착점 (N-1, N-1)에 도착할 수 있다면 “도착!”을 출력하라.

import java.util.LinkedList;

/*
(예시 문제)
N×N 크기의 미로가 있다. 미로는 0과 1로 이루어져 있으며,
1은 이동할 수 있는 길, 0은 벽을 의미한다.
시작점은 항상 왼쪽 위 (0, 0)이고, 도착점은 오른쪽 아래 (N-1, N-1)이다.
현재 위치에서 상, 하, 좌, 우로만 이동할 수 있다.

1️⃣ (0,0)부터 출발해서 이동 가능한 모든 칸을 탐색하라.
2️⃣ 이동 가능한 칸을 방문 순서대로 출력하라.
3️⃣ 도착점 (N-1, N-1)에 도착할 수 있다면 “도착!”을 출력하라.
 */
public class DFS_study_2 {

    static int[][] maze ={
            {1,0,1,1},
            {1,1,1,0},
            {0,1,0,1},
            {1,1,1,1}
    };
    static int n = maze.length;
    static boolean[][] isVisited = new boolean[n][n];

    // 상하좌우 좌표
    static int[] dx= {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static void DFS(int x, int y){
        if (x<0 || y<0 || x>=n || y>=n || maze[x][y]==0){
            return;
        }
        isVisited[x][y] = true;
        System.out.println("("+x+","+y+")");
        
        for (int i=0; i<4; i++){
            DFS(x+dx[i], y+dy[i]);
        }
    }
}

 

DFS를 이용해 구현하였다. 

dfs(x,y)가 호출될 떄마다

현재 칸을 방문하고 인접한 칸(상하좌우)를 재귀적으로 탐색한다. 

 

 

 

 

그렇다면 백트래킹 이란?

DFS를 기반으로 하되, 조건 검사를 추가해 불필요한 경로는 미리 차단(되돌아감) 하는 방법을 말한다.

 

쉽게 말하면,
"갈수 있는 길만 가고, 막히면 돌아온다" 는 원리이다.

 

 

다음은 백트래킹으로 구현한 미로찾기 문제이다.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class MazeBackTracking {

    static int[][] maze ={
            {1,0,1,1},
            {1,1,1,0},
            {0,1,0,1},
            {1,1,1,1}
    };
    static int n = maze.length;
    static boolean[][] isVisited = new boolean[n][n];

    // 상하좌우 좌표
    static int[] dx= {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    //현재까지의 경로를 저장하는 리스트. 각 원소는 {x,y} 좌표 배열이다.
    static List<int[]> path = new ArrayList<>();

    public static void main(String[] args) {
        if (backtrack(0,0)){
            System.out.println("경로 찾음");
            for (int[] p: path){
                System.out.println(p[0] + ","+p[1]);
            }
        }
        else{
            System.out.println("경로를 찾지 못함");
        }

    }

    static boolean backtrack(int x, int y){
        if (x<0 || y<0 || x>=n || y>=n || maze[x][y]==0 || isVisited[x][y]){
            return false;
        }
        isVisited[x][y]=true;
        path.add(new int[]{x,y});

        if (x== n-1 && y== n-1){
            return true;
            // 현재 칸이 도착지라면 path는 완성한 경로를 담고있고 true를 반환한다.
            // 전체 탐색을 종료한다.
        }

        for (int i=0; i<4; i++){
            if(backtrack(x+dx[i],y+dy[i]))
                return true;
            // 하나의 성공 경로를 찾으면 더이상 탐색하지 않는다.
        }
        
        path.remove(path.size()-1);
        isVisited[x][y]=false;
        return false;
    }
}

 

isVisited[x][y]=false로 되돌리는 이유는?

 

재귀를 통해 한 경로를 시도할 때에는 같은 경로 내에서 중복 방문을 막아야 한다.

하지만 다른 경로에서 이 칸을 다시 사용하려면 방문 표시를 풀어주어야 한다.

따라서 백트래킹은 상태 변경(방문 표시, path 추가)을 하고, 실패 시 원상 복구한다.

 

 

 

경로를 찾으면 path 리스트에 경로(좌표들)를 순서대로 저장하고 true를 반환해서 더이상의 탐색을 멈춘다.

더이상 진행이 불가능하면, path에서 제거하고 이전 노드로 백트랙한다.

 

 

 

 

정리!
DFS는 탐색 자체의 기법이고, 백트래킹은 "필요없는 경로는 탐색 안하기"를 더한 전략이다.