미로탐색(DFS)

최준호·2021년 10월 6일
0

알고리즘 강의

목록 보기
70/79

문제

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.

출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다.

격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

코드

public class Maze {
    static int[][] maze = new int[8][8];
    static int answer = 0;
    static int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i=1; i<8; i++){
            for(int j=1; j<8; j++){
                maze[i][j] = sc.nextInt();
            }
        }

        dfs(1,1);

        System.out.println(answer);
    }
    public static void dfs(int x, int y){
        if(x>7 || y>7 || x<1 || y<1) return;
        if(maze[x][y] == 1) return;
        if(x==7 && y==7){
            answer++;
        }else{
            for(int[] dir : direction){
                maze[x][y] = 1;
                dfs(x+dir[0], y+dir[1]);
                maze[x][y] = 0;
            }
        }
    }
}

설명

강사님의 코드와 전체적인 로직은 차이가 없었다. 7*7 격자 크기의 미로를 만들기 위해 maze라는 2차원 배열을 [8][8]로 만든다. 그 이유는 0 index를 사용하지 않고 1~7만 사용하기 위함이다. 이건 따로 설명 안하겠다. 그리고 direction을 2차원 배열로 지정해놨는데 1차 배열 2개를 x,y로 만들어서 사용해도 되고 나처럼 2차원 배열로 미리 넣어놔도 된다. 2차원 배열 안에 들어있는 값의 의미는 북,동,남,서 방향으로 4가지 방향을 탐색하기 위함인데 dfs 파라미터를 보면 값들의 좌표 값을 변경한다는 것을 바로 알수 있다.

dfs내의 백트래킹 조건을 확인해보자.

  1. 격자의 범위를 벗어난다면 dfs는 종료된다.
  2. 해당 좌표 배열의 값이 1일 경우에도 벽을 만났거나 이미 지나온 길이므로 dfs는 종료된다.

위 백트래킹 조건을 모두 만족하지 않는다면 현재 좌표값이 7,7인지 확인한다. 7,7이면 출구에 도착한 것이므로 answer의 값을 증가시키고 그렇지 않다면 아직 탐색 중이므로 지금 현재 밟고 있는 좌표는 1로 표시하여 되돌아 오지 않도록 하고 dfs를 실행한 뒤 현재 좌표를 0으로 다시 롤백해주어 돌아가는 경우를 만든다.

이전에 미로 탐색 DFS 문제를 풀어봤었어서 쉽게 풀어볼 수 있었다. 그래도 예전에 풀었을 때는 과정을 이해를 하지 못하고 그저 코드를 따라치기만 한 수준이였는데 이번 문제 풀이는 로직의 동작 과정을 이해하면서 문제를 풀어내서 기분이 좋았다!

profile
코딩을 깔끔하게 하고 싶어하는 초보 개발자 (편하게 글을 쓰기위해 반말체를 사용하고 있습니다! 양해 부탁드려요!) 현재 KakaoVX 근무중입니다!

0개의 댓글