미로의 최단거리 통로(BFS, Queue)

문제설명

7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하세요. 경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로의 길이는 12이다.

입력 설명

• 첫 번째 줄부터 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 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

출력예제

12

내 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Point{
    int x;
    int y;
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main_8_11 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int[][] arr, dis;
    void bfs(int x, int y){
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x,y));
        arr[x][y] = 1;
        while(!q.isEmpty()){
            Point tmp = q.poll(); // tmp는 현재지점
            for(int i = 0 ; i < 4; i++){
                int px = tmp.x + dx[i];
                int py = tmp.y + dy[i];
                if(px >= 1 && px < arr.length && py >= 1 && py < arr.length && arr[px][py] == 0 ){ //조건 및 경계선 체크
                    arr[px][py] = 1;
                    q.offer(new Point(px, py));
                    dis[px][py] = dis[tmp.x][tmp.y] + 1; // count를 세기 위해
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Main_8_11 t = new Main_8_11();
        Scanner kb = new Scanner(System.in);
        arr = new int[8][8];
        dis = new int[8][8]; //
        for(int i = 1; i < arr.length;i++){
            for(int j = 1; j < arr.length;j++){
                arr[i][j] = kb.nextInt();
            }
        }
        t.bfs(1,1); //출발점
        if(dis[7][7] == 0) // 만약 도착하지 못하여 도착점이 0
            System.out.println(-1);
        else // 도착점에 도착한다면 도착점에 값 출력
            System.out.println(dis[7][7]);
    }
}

• BFS를 활용하여 풀어보았다.
• 미로의 x좌표와 y좌표를 입력하기 위해 Point라는 클래스를 생성해주었다.
• 현재 좌표 기준 동, 서, 남, 북의 좌표가 0이고 미로(arr 배열)의 범위(1 ~ 7까지)를 벗어나지 않는다면 해당 좌표를 1로 체크해주고 dis 배열에 이전 좌표의 값 +1 을 해준다.
• 만약 dis[7][7]에 도착했을 때 해당 값이 0이면 -1을 출력해 도착할 수 없음을 나타내고 dis[7][7]이 0이 아니라면 해당 값이 최단 경로이다.