미로의 최단거리 BFS_ 알고리즘

문제

접근법

처음에는 미로문제와 같이 DFS형식으로 접근해야 하는지 알았는데, 해설을 보다보니 결국 결과까지는 모든 깊이의 경로를 파악해야하기 때문에 BFS를 사용해야한다.

구현의 형식이 BFS또한 DFS와 유사한 면이 있는 것 같다.

1. Queue객체 생성 -> Type은 x값과 y값 둘다 체크해야되기 때문에 Point라는 클래스를 생성해 x,y변수를 담는다.

2. queue객체에 첫번째 시작점 offer

3. arr배열에도 시작점을 1로 초기화

4. while문 생성(queue가 empty할때까지)

5. 현재위치Point poll로 꺼내기

6. for문 move(UP,DOWN,LEFT,RIGHT)까지 체크

7. 다음x, 다음y 변수에 현재.x + move.x , 현재.y + move.y 대입

8. if문을 통해 다음위치가 배열의 바깥으로 나가는지 체크 && 다음위치가 갈 수 있는 곳(0)인지 체크

9. arr[다음x][다음y]=1로 변경

10. queue에 다음위치 offer

11. distance배열 [다음x][다음y] = 현재 x, y값 + 1

코드

package Problem;

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

public class 미로의최단거리통로_BFS {

    static int arr[][] = new int[7][7];
    static int dis[][] = new int[7][7];

    static int move[][] = {{0,1},{0,-1},{1,0},{-1,0}};

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

        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[0].length; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        BFS(0,0);

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

    /**
     *  BFS는 Queue를 통해 구현
     *  
     *  1. Queue객체 정의 후 생성 -> Type은 x값과 y값을 둘다 넣어야 하기 때문에 Point클래스 생성
     *  2. queue객체에 첫번째 시작점 넣기
     *  3. arr배열에도 시작저 1로 변경
     *  4. while문 생성(queue가 빌때까지 돌기)
     *  5. queue.poll()해서 큐 꺼내기
     *  6. for문 동작해서 move(위,아래,좌,우) 전부 체크
     *  7. 다음 x값, 다음 y값 좌표 변경
     *  8. if문을 통해 arr범위의 바깥인지 체크
     *  9. arr다음 위치 1로 변경
     *  10. queue에 다음 위치좌표들 offer
     *  11. distance체크 배열에도 이전 배열카운트 + 1해서 체킹
     * */
    static void BFS(int x, int y){
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        arr[x][y]=1;

        while(!queue.isEmpty()){
            Point tmp =queue.poll();

            for(int i=0; i<move.length; i++) {
                int nx = tmp.x + move[i][0];
                int ny = tmp.y + move[i][1];

                if(nx>=0 && ny>=0 && ny<arr.length && nx<arr.length && arr[nx][ny]==0) {
                    arr[nx][ny]=1;
                    queue.offer(new Point(nx,ny));
                    dis[nx][ny]=dis[tmp.x][tmp.y]+1;
                }
            }

        }

    }

    static class Point{
        int x;
        int y;

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

}