미로의 최단거리(BFS)

뭔가 기존 자료형으로 안될거 같으면 클래스를 만들어서 사용해보자

 

7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력

입력

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

 

출력. 도착할 수 없으면 -1를 출력한다.

12

 

풀이

 

 

 

한 지점에서 상하좌우 지점으로 이동하는 것을 레벨 탐색으로 생각하고 board 배열 이동 횟수를 저장할 dis 배열을 만든 후

이동할때마다 기존 배열의 이동횟수 +1을 하면서 레벨 탐색한다, 마지막에 dis[7][7] 칸이 0이면 마지막 칸 까지 도달한 방법이 없는거라 -1, 아니면 dis[7][7]의 값을 리턴한다

 

 

일단 좌표를 저장할 Pointer 클래스를 만들어준다

 

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

 

 

BFS함수에서는 처음에 1,1 좌표를 받아오니 큐에 1,1 좌표를 넣고 큐가 비어있지 않은(갈 곳이 있는) 상태일때마다 큐에 넣어주고 그 칸의 이동횟수를 현재 이동횟수 +1로 만들면서 탐색한다

public void BFS(int x, int y){
        Queue<Point> Q = new LinkedList<>();
        Q.add(new Point(x,y));
        board[x][y] = 1;
        int L = 0;

        while (!Q.isEmpty()){
            Point tmp = Q.poll();
            for (int i = 0; i <4; i++){
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board[nx][ny] == 0){
                    Q.add(new Point(nx,ny));
                    board[nx][ny] = 1;
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }

 

전체 코드

 

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

public class Main {
    static int max = -1;
    static int[][] board;
    static int[][] dis; // 이동횟수를 저장할 배열
    static int[] dx= {-1, 0, 1, 0};
    static  int[] dy = {0, 1, 0, -1};

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

    public void Solution(){

    }

    public void BFS(int x, int y){
        Queue<Point> Q = new LinkedList<>();
        Q.add(new Point(x,y));
        board[x][y] = 1;
        int L = 0;

        while (!Q.isEmpty()){
            Point tmp = Q.poll();
            for (int i = 0; i <4; i++){
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board[nx][ny] == 0){
                    Q.add(new Point(nx,ny));
                    board[nx][ny] = 1;
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Main T = new Main();

        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] = in.nextInt();
        }

        T.BFS(1,1);

        if (dis[7][7] == 0) System.out.println(-1);
        else System.out.println(dis[7][7]);
    }
}