문제

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

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

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

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

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

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

코드

public class Maze {
    static int[][] maze, check;
    static int[][] direction = {{-1,0},{0,1},{1,0},{0,-1}};

    public static void main(String[] args) {
        maze = new int[8][8];
        check = new int[8][8];

        Scanner sc = new Scanner(System.in);
        for(int i=1; i<8; i++){
            for(int j=1; j<8; j++){
                maze[i][j] = sc.nextInt();
            }
        }

        bfs(1,1);
        int result = check[7][7];
        if(result == 0) System.out.println(-1);
        else System.out.println(result);
    }

    public static void bfs(int x, int y){
        Queue<Pointer> que = new LinkedList<>();
        que.offer(new Pointer(x,y));

        while(!que.isEmpty()){
            Pointer p = que.poll();
            for(int[] dir : direction){
                int nx = p.x + dir[0];
                int ny = p.y + dir[1];
                if(nx>0 && nx<8 && ny>0 && ny<8 && maze[nx][ny] != 1){
                    check[nx][ny] = check[p.x][p.y] + 1;
                    maze[nx][ny] = 1;
                    que.offer(new Pointer(nx, ny));
                }
            }
        }
    }

    static class Pointer{
        int x;
        int y;

        public Pointer(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

설명

bfs로 미로의 최단거리를 찾는 문제다. bfs는 queue를 사용하여 큐에 계속해서 탐색할 값을 넣어주고 해당 큐를 통해서 while을 돌려 답이 나올때까지 탐색을 진행하는 경우인데 dfs와 다른 점은 dfs는 재귀를 통해서 로직을 구성한다면 bfs는 while문 안에서 로직을 구성한다는 것이다.

해당 문제는 시작 전에 Pointer라는 class와 check[][] 2차원 배열을 만들어야한다. 그 이유는 큐에 담아서 사용할 Pointer class가 Node의 역할을 대신하며 check 2차원 배열은 우리가 지나온 길이 몇번만에 도착했는지 알수 있게 해준다.

bfs문제는 아직 많이 접해보지 못해서 문제를 보고 바로 알고리즘의 틀이 떠오르지 않는다 좀 더 풀어서 dfs처럼 문제 보면서 틀이 바로 떠올릴 수 있도록 하자!