[코딩 문제] 미로 탐색

문제

N x N 크기의 배열로 표현되는 미로가 있다.

int[][] maze = {
    {0,0,1,0,0},
    {1,0,0,0,1},
    {0,1,1,0,0},
    {1,0,0,0,0},
    {0,0,1,0,0}
}

 

미로에서 0은 이동할 수 있는 칸을 나타내고, 1은 이동할 수 없는 칸을 나타낸다. 이런 미로가 주어졌을 때 (0, 0)에서 출발하여 (N, N)의 위치로 이동할 수 있는지 없는지의 여부를 판단하는 프로그램을 작성하라.

 

규칙

• 10 x 10 배열을 임의로 생성하여 사용한다. (프롬프트에서 입력 받아 생성하는 등의 방법을 사용하지 않으며, 배열의 선언은 코드에 포함된다)
• 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동할 수 있다.
• 9,9 배열로 이동할 수 있으면 "Pass"를 출력하고, 없으면 "Fail"을 출력한다.
• 소스코드는 한글을 포함하지 않는다.
• 패키지를 지정하지 않는다.
• 메시지와 이동한 칸의 수를 함께 출력한다. 출력의 모양은 아래와 같다.

/* 성공 */
Pass, 14

/* 실패 */
Fail, 21

 

코드

public class Maze {
    // java에서 변수 선언 앞에 static 쓰면 전역변수됨
    static int[][] maze = { 
        {0,0,1,0,0,0,0,1,0,0},
        {1,0,0,0,1,1,0,0,0,1},
        {0,1,1,0,0,0,1,1,0,0},
        {1,0,0,0,0,1,0,0,0,0},
        {0,0,1,0,0,0,0,1,0,0},
        {0,0,1,0,0,0,0,1,0,0},
        {1,0,0,0,1,1,0,0,0,1},
        {0,1,1,0,0,0,1,1,0,0},
        {1,0,0,0,0,1,0,0,0,0},
        {0,0,1,0,0,0,0,1,0,0}
    };

    static boolean[][] visited = new boolean[10][10]; // 방문했던 곳, boolean은 초기값 false
    static int count = 0;
    static boolean end; // [9][9] 도착하면 true -> pass

    public static void main(String[] args) {

        search(0,0); // [0][0] 부터 시작

        if(end) {
            System.out.println("Pass, " + count);
        }
        else {
            System.out.println("Fail, " + count);
        }
    }

    static void search(int r, int c) {
        // 자바에서 if문에서 return 쓰면 함수 종료
        if (r<0 || r>=10 || c<0 || c>=10 || visited[r][c] || maze[r][c] == 1) {
            return; 
        }

        visited[r][c] = true;
        count++;

        if (r==9 && c==9) {
            end = true;
            return;
        }

        search(r-1, c); // 상
        search(r+1, c); // 하
        search(r, c-1); // 좌
        search(r, c+1); // 우
    }
}

 

실행 결과

Pass, 70

 

 

---

 

 

출처: https://github.com/gikpreet/class-programming_with_java/tree/master

GitHub - gikpreet/class-programming_with_java