미로 탐색 (DFS)

설명

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

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

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

 

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

 

입력

7*7 격자판의 정보가 주어집니다.

 

출력

첫 번째 줄에 경로의 가지수를 출력한다.

 

예시 입력 1 

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

 

예시 출력 1

8

 

 

문제 해결

 

7 x 7로 정해진 미로를 탈출하는 경로의 가지수를 구해 출력하는 문제이다.

static int[][] maze;
static int count = 0;
static int[] dx = {-1, 1 ,0 ,0}; //x좌표 이동
static int[] dy = {0, 0, -1, 1}; //y좌표 이동
static boolean[][] visited;

• 7x7 격자판 미로는 2차원 배열이므로 2차원 배열을 저장할 수 있는 maze 배열을 선언한다.
• 경로의 가지수를 저장할 count와 
• 상하좌우로 이동하는 이동 방향을 나타내는 배열인 dx, dy도 선언해준다.
• 방문여부를 저장할 visited 배열이다. 격자판 위의 위치를 나타내므로 이또한 2차원 배열로 선언해준다!

 

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    maze = new int[7][7];
    visited = new boolean[7][7];

    for(int i = 0; i < 7; i++) {
        for(int j = 0; j < 7; j++) {
            maze[i][j] = in.nextInt();
        }
    }

    visited[0][0] = true;
    DSF(0,0);
    System.out.println(count);

}

• 7x7 격자판 숫자들을 입력받아준 후
• 시작점 (0, 0)을 방문표시하고, DFS를 호출한다.

 

public static void DSF(int x, int y) {
    if(x == 6 && y == 6){
        count++; //도착점에 도착하면 count 증가
        return;
    }

    for (int i = 0; i < 4; i++) { //상하좌우 4가지로 이동 가능
        int nx = x + dx[i]; //새로운 x좌표 생성
        int ny = y + dy[i]; //새로운 y좌표 생성

        //새로운 만든 좌표가 범위를 벗어나면 continue
        if (nx < 0 || ny < 0 || nx >= 7 || ny >= 7) continue;
        // 방문한 적이 있거나 벽인 경우 continue
        if (visited[nx][ny] || maze[nx][ny] == 1) continue;

        visited[nx][ny] = true;
        DSF(nx, ny);
        visited[nx][ny] = false;
    }

}

• 도착점은 (6, 6)이다. 출발점에서 이 도착점까지 도달할 수 있는 경로를 탐색하는 함수이다.
• 이미 도착점이면 경로를 하나 찾은 것이므로 count를 하나 올려주고 return한다.
• 상하좌우 네 방향으로 이동할 수 있으므로 다음과 같이 for문으로 돌며 새로운 x좌표와 y좌표를 계산해준다.
  • IF 새로운 좌표가 격자판 범위를 벗어나거나, 이미 방문한 적이 있거나, 벽인 경우는 countinue해준다.
  • 위 경우가 아니면 새로운 좌표에 방문 표시를 하고, DSF 메서드로 새로운 좌표를 넘겨 호출하여 다음 위치로 이동하면 된다.
  • 그리고 다시 방문 표시 false로 돌려주기!

 

최종 코드

 

import java.util.Scanner;

public class P10_미로탐색_DFS {
    static int[][] maze;
    static int count = 0;
    static int[] dx = {-1, 1 ,0 ,0}; //x좌표 이동
    static int[] dy = {0, 0, -1, 1}; //y좌표 이동
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        maze = new int[7][7];
        visited = new boolean[7][7];

        for(int i = 0; i < 7; i++) {
            for(int j = 0; j < 7; j++) {
                maze[i][j] = in.nextInt();
            }
        }

        visited[0][0] = true;
        DSF(0,0);
        System.out.println(count);

    }

    public static void DSF(int x, int y) {
        if(x == 6 && y == 6){
            count++; //도착점에 도착하면 count 증가
            return;
        }

        for (int i = 0; i < 4; i++) { //상하좌우 4가지로 이동 가능
            int nx = x + dx[i]; //새로운 x좌표 생성
            int ny = y + dy[i]; //새로운 y좌표 생성

            //새로운 만든 좌표가 범위를 벗어나면 continue
            if (nx < 0 || ny < 0 || nx >= 7 || ny >= 7) continue;
            // 방문한 적이 있거나 벽인 경우 continue
            if (visited[nx][ny] || maze[nx][ny] == 1) continue;

            visited[nx][ny] = true;
            DSF(nx, ny);
            visited[nx][ny] = false;
        }

    }
}