[Algorithm] 미로의 최단거리 통로(BFS)

설명

7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하세요.

경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다.

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

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

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

 

입력

첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

 

출력

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

 

 

 

풀이 과정.

좌표(1,1)부터 시작해서 상하좌우 0을 확인 후 Queue에 담으면서 진행.

위 그림좌표와 같은 크기의 2차원 확인배열 하나 만든다.

기존배열은 1칸 씩 이동할 때 마다 기존 좌표의 값을 1로 처리해준다.

확인배열은 1칸 씩 이동할 때 마다 기존 좌표의 값+1을 처리해준다. (좌표 0,0부터 1씩 누적 된다)

제일 먼저 좌표(7,7)에 도착하면 좌표 값을 1로 만들어 차후에 도착하는 친구?들은 도착하지 못하게 한다.

(최단거리는 이미 도착했으므로 차후 도착하는 친구들은 필요 없다. 단지 Queue만 비우기위해 반복된다.)

 

풀이.

public class Main {

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

    static Queue<Point> Q = new LinkedList<>();
    static int[][] board; // 실제 좌표 값 배열 (지나간곳은 벽=1 처리)
    static int[][] dis; // 좌표 크기의 빈 배열 (거리 누적)
    static int[] dx = {-1, 1, 0, 0}; // 상 하
    static int[] dy = {0, 0, -1, 1}; // 좌 우

    static void BFS(int x, int y){
        Q.offer(new Point(x,y)); // 시작점 1,1, 넣는다.
        board[x][y] = 1; // 시작점 벽 처리.

        while (!Q.isEmpty()){
            Point temp = Q.poll(); // 큐에서 하나 꺼내고
            for (int i = 0; i < 4; i++) {
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];
                if(nx >= 1 && nx <= 7  && ny >=1 && ny <= 7 && board[nx][ny] == 0){
                    Q.offer(new Point(nx,ny)); // Q에서 넣고
                    board[nx][ny] = 1; // 벽 처리
                    dis[nx][ny] = dis[temp.x][temp.y]+1; // 거리누적
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        board = new int[8][8];
        dis = new int[8][8];
        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        BFS(1,1);
        if(dis[7][7] == 0){
            System.out.println("-1");
        }else{
            System.out.println(dis[7][7]);
        }
    }
}

 

---

 

정리 :

마지막 좌표 7,7에 최초 도착 시 좌표값을 1로 처리하여 차후 도착하려는 친구들은 도착하지 못하도록 만든다.