Java DFS를 이용한 미로 탐색

Java DFS를 이용한 미로 탐색

Java로 DFS(Depth First Search)를 이용하여 간단한 미로 탐색을 구현하는 방법에 대해 알아보겠습니다.

1. 미로의 탐색

위와 같은 미로가 있다고 했을 때 탐색을 위해서는 출발 정점과 도착 정점의 설정이 필요합니다. S를 출발 정점, F를 도착 정점이라고 했을 때 S부터 F까지 도달 가능한 모든 경로를 구하고 이 중에서 최단 경로의 값을 구하는 방법에 대해 알아보겠습니다.

2. DFS를 이용한 미로 탐색 구현

이전에 깊이 우선 탐색(DFS)에 대해서 정리한 내용을 간단히 설명하면, DFS는 출발 정점부터 시작하여 최대한 깊숙히 탐색 후 원점으로 돌아가서 다른 정점을 탐색하는 방식입니다.

미로 탐색에 사용하는 DFS의 조건은 다음과 같습니다.

• 미로 탐색시 한 방향으로 갈 수 있을 때까지 계속 탐색
  막다른 곳에 도달하면 막다른 길에 대한 표식을 남기고 가장 가까운 갈림길로 돌아와 다시 탐색을 진행.
  이러한 방법으로 갈림길을 순차적으로 탐색하여 목적지까지의 경로를 구함.
• 넓게(Breadth) 탐색하기 전에 깊게(Depth) 탐색
• 모든 노드를 방문하고자 하는 경우에 사용
  
• 자기 자신을 호출하는 순환 알고리즘의 형태 (재귀호출)
• 노드 방문 여부를 반드시 검사해야 함
  이렇게 하지 않을 경우 무한 루프에 빠질 위험이 있음

DFS 미로 탐색은 스택, 인접 행렬, 인접 리스트를 이용해서도 구현이 가능하지만 위의 조건과 재귀호출만을 이용하여 구현해보도록 하겠습니다.

다음은 재귀호출로 구현한 DFS 소스코드입니다.

/*
 * @ TITLE DFS 미로 탐색
 * @ COMMENT
 *     재귀호출을 이용한 탐색 구현
 */
// DFS 그래프 클래스
class DfsGraph {
    
    public static int MAZE_SIZE = 7;    // 미로의 크기
    public static int MIN = MAZE_SIZE * MAZE_SIZE;    // 경로의 최소값 설정 (최초 설정 값은 미로의 최대 탐색 경로로 설정)
    public static int GOAL_Y = 5, GOAL_X = 6;    // 목표 정점의 y,x 좌표
    public static int SEARCH_CNT = 0;    // 미로 탐색 회차
    public String[][] maze = new String[MAZE_SIZE][MAZE_SIZE];    // 미로를 생성할 2차원 배열
 
    // DFS 탐색
    public void dfsMazeSearch(int y, int x, int l) {
 
        // 목표 정점에 도착했을 경우
        if (y == GOAL_Y && x == GOAL_X) {
            
            ++SEARCH_CNT;
            System.out.println("\n[ " + SEARCH_CNT + "차 미로 탐색 종료 ]\n");
            
            // 목표 정점에 도착했음을 표시하기 위해 '*'을 값으로 설정
            maze[y][x] = "*";
            
            for(int i=0; i<maze.length; i++) {
                for(int j=0; j<maze[i].length; j++) {
                    System.out.print(maze[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();
            
            // 최단 경로값이 l보다 크면, l이 작은 것이므로 l을 최단 경로값으로 지정
            if (MIN > l) {
                MIN = l;
            }
            
            // 되돌아갈 경우
            // 방문했던 좌표를 방문가능한 상태로 되돌리기 위해 '□'을 값으로 설정
            maze[y][x] = "□";
            System.out.print("back ");
            return;
        }
        
        // 해당 좌표를 방문했음을 표시하기 위해 '*'을 값으로 설정
        // 배열에서는 y가 세로축, x가 가로축이 되므로 반대로 좌표값을 입력
        maze[y][x] = "*";
        
        // 미로의 상하좌우 탐색
        // 방문한 좌표값 : '*'
        // 방문 불가능한 좌표값 : '■'
        // 방문 가능한 좌표값 : '□'
        // 해당 좌표로 이동이 가능할 경우, 이동할 좌표를 설정하고 길이를 1 증가시켜 dfsMazeSearch() 호출
        
        // 위로 이동
        // y축 좌표가 0보다 크고, 이동할 좌표의 값이 '*'과 '■'이 아닌 경우
        if (y > 0 && !maze[y-1][x].equals("*") && !maze[y-1][x].equals("■")) {
            System.out.print("↑ up ");
            dfsMazeSearch(y-1, x, l+1);
        }
        // 아래로 이동
        // y축 좌표가 미로의 세로 길이보다 작고, 이동할 좌표의 값이 '*'과 '■'이 아닌 경우
        if (y < MAZE_SIZE-1 && !maze[y+1][x].equals("*") && !maze[y+1][x].equals("■")) {
            System.out.print("↓ down ");
            dfsMazeSearch(y+1, x, l+1);
        }
        // 왼쪽으로 이동
        // x축 좌표가 0보다 크고, 이동할 좌표의 값이 '*'과 '■'이 아닌 경우
        if (x > 0 && !maze[y][x-1].equals("*") && !maze[y][x-1].equals("■")) {
            System.out.print("← left ");
            dfsMazeSearch(y, x-1, l+1);
        }
        // 오른쪽으로 이동
        // x축 좌표가 미로의 가로 길이보다 작고, 이동할 좌표의 값이 '*'과 '■'이 아닌 경우
        if (x < MAZE_SIZE-1 && !maze[y][x+1].equals("*") && !maze[y][x+1].equals("■")) {
            System.out.print("→ right ");
            dfsMazeSearch(y, x+1, l+1);
        }
     
        // 되돌아갈 경우
        // 방문했던 좌표를 방문가능한 상태로 되돌리기 위해 '□'을 값으로 설정
        maze[y][x] = "□";
        System.out.print("back ");
        return ;
    }
 
}
    
public class DFSMaze {
    public static void main(String[] args) {
        
        DfsGraph dfsGraph = new DfsGraph();
        
        // 미로 생성
        for(int i=0; i<dfsGraph.maze.length; i++) {
            for(int j=0; j<dfsGraph.maze[i].length; j++) {
                dfsGraph.maze[i][j] = (i == 0 || i == DfsGraph.MAZE_SIZE-1 || j == 0 || j == DfsGraph.MAZE_SIZE-1) ? "■" : "□";
            }
        }
        
        // 미로에서 이동이 불가능한 좌표 설정
        dfsGraph.maze[1][0] = "□";
        dfsGraph.maze[5][6] = "□";
        dfsGraph.maze[2][1] = "■";
        dfsGraph.maze[2][2] = "■";
        dfsGraph.maze[2][3] = "■";
        dfsGraph.maze[2][4] = "■";
        dfsGraph.maze[4][2] = "■";
        dfsGraph.maze[4][4] = "■";
        dfsGraph.maze[4][5] = "■";
        
        // 생성된 초기 미로 출력
        System.out.println("[ 초기 생성 미로 ]");
        for(int i=0; i<dfsGraph.maze.length; i++) {
            for(int j=0; j<dfsGraph.maze[i].length; j++) {
                System.out.print(dfsGraph.maze[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
        
        // 미로의 좌표와 길이 l을 매개변수로 dfsMazeSearch() 호출
        // 생성한 미로에서 maza[1][0] 지점부터 탐색 시작
        // 경로의 길이 비교에 사용할 l의 초기값은 '1'로 설정
        dfsGraph.dfsMazeSearch(1, 0, 1);
        
        // 최단 경로값 출력
        System.out.println("\n\n미로의 최단 경로값 : " + DfsGraph.MIN);
        
    }
}

실행 결과는 다음과 같습니다.

미로의 각 영역은 다음과 같이 설정하였습니다. 

• ■ : 방문 불가능한 좌표
  
• □ : 방문 가능한 좌표
• * : 방문한 좌표

또한 실행 결과에 출력된 내용을 확인해보면 재귀호출에 따라 상하좌우 이동이 이루어지는 것과 도착 정점에 도달했을 경우 최단 경로값 설정이 어떻게 이루어지는지 확인할 수 있습니다. 

구현 전에 정의한 DFS 미로 탐색 조건과 함께 코드를 보면 순차적으로 어떻게 탐색이 이루어지는지 확인하실 수 있습니다. 좀 더 설명이 필요한 부분은 코드가 실행되는 각 부분에 주석을 함께 작성하였습니다.

이상으로 Java DFS를 이용한 미로 탐색 구현 방법에 대해 알아봤습니다.

※ 참고 문헌

• bumbums.tistory.com, DFS (깊이우선탐색) 이용한 가능한 모든 경로 구하기, https://bumbums.tistory.com/1

• roxxy.tistory.com, 깊이 우선 탐색(DFS, Depth First Search), https://roxxy.tistory.com/entry/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-Depth-First-Search