미로찾기

미로찾기

 

문제

---

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 출력하는 프로그램을 작성하시오. 아래 그림에 대하여 S에서 E까지 가는 최단거리는 22이다.

 

입력

---

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

 

출력

---

(N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다.

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0 1 0
0 1 1 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력

22







코드 // BFS써야함

// 미로찾기 BFS

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

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static int count = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c[][];

        a = sc.nextInt();
        b = sc.nextInt();

        c = new int[a + 1][b + 1];

        int input = 0;
        for (int i = 1; i <= a; i++) {
            for (int j = 1; j <= b; j++) {
                input = sc.nextInt();
                if (input == 1) c[i][j] = -1;
                else c[i][j] = input;
            }
        }

        sc.close();

        findGoalBFS(c, a, 1);

        System.out.println(c[1][b]);


    }

    public static void findGoalBFS(int[][] c, int a, int b) {
        Queue<int[]> q = new LinkedList<>();

        c[a][b] = 0;
        int[] data;
        data = new int[]{a, b, 0};
        q.offer(data);

        while (!q.isEmpty()) {

            data = q.poll();

            int[][] dataS = new int[4][3];
            dataS[0] = new int[]{data[0] - 1, data[1], data[2] + 1};
            dataS[1] = new int[]{data[0], data[1] + 1, data[2] + 1};
            dataS[2] = new int[]{data[0], data[1] - 1, data[2] + 1};
            dataS[3] = new int[]{data[0] + 1, data[1], data[2] + 1};

            for (int i = 0; i < 4; i++) {

                int[] da = dataS[i];

                if (da[0] <= 0 || da[0] >= c.length || da[1] >= c[0].length || da[1] <= 0 || c[da[0]][da[1]] == -1) ;
                else if (c[da[0]][da[1]] == 0 || c[da[0]][da[1]] > da[2]) {
                    c[da[0]][da[1]] = da[2];
                    q.offer(da);
                }
            }


        }


    }


    public static void findGoalDFS(int[][] c, int a, int b, int length) {

        if (a <= 0 || b <= 0 || a >= c.length || b >= c[0].length || c[a][b] == -1) return;

        if (a == 1 && b == c[0].length - 1) {
            if (c[a][b] == 0 || length < c[a][b]) c[a][b] = length;
            return;
        }

        if (c[a][b] == 0 || c[a][b] > length) c[a][b] = length;
        else return;

        findGoalDFS(c, a - 1, b, length + 1);
        findGoalDFS(c, a, b + 1, length + 1);
        findGoalDFS(c, a + 1, b, length + 1);
        findGoalDFS(c, a, b - 1, length + 1);

    }

}