[알고리즘] 미로 탈출 (구현)

문제

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

 

---

 

입력 조건

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0 또는 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

 

---

 

출력 조건

 

첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

 

---

풀이

간선의 비용이 똑같은 노드의 최단거리는 BFS를 사용하여 푸는것이 좋다!!!!

 

 

public class Problem2 {
    static int N;
    static int M;
    static int MIN=Integer.MAX_VALUE;

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    //0은 못가, 1은 가

    //최소 칸의 개수 ==> 넓이우선 DFS
    //시작칸과 마지막 칸의 개수



    public static void main(String[] args) {


        try(BufferedReader br =new BufferedReader(new InputStreamReader(System.in))){


            int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            N = inputs[0];
            M = inputs[1];

            for(int i=0; i< N; i++){//맵 설정 완료
                graph.add(new ArrayList<>(Arrays.stream(br.readLine().split("")).map(Integer::parseInt).toList()));
            }

            System.out.println(bfs(0,0));


        } catch (IOException e) {
            e.printStackTrace();
        }


    }

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

    private static int bfs(int i, int j) {

        Deque<ArrayList<Integer>> queue= new ArrayDeque<>();

        queue.addFirst(new ArrayList<>(Arrays.asList(i,j)));



        while (!queue.isEmpty()){
            ArrayList<Integer> pos = queue.poll();
            int x = pos.get(0);
            int y = pos.get(1);

            for(int k=0; k< 4; k++) {
                int dx = x + step[k][0];
                int dy = y + step[k][1];


                if (dx < 0 || dx >= N || dy < 0 || dy >= M) {
                    continue;
                }
                if (graph.get(dx).get(dy).equals(0)) {
                    continue;
                }
                //graph.get(nx).set(ny,0);

                if (graph.get(dx).get(dy).equals(1)) {//1이라면
                    graph.get(dx).set(dy,graph.get(x).get(y)+1);
                    queue.addFirst(new ArrayList<>(Arrays.asList(dx,dy)));
                }

            }

        }

        return graph.get(N-1).get(M-1);


    }

}

 

 

 

 

 

 

 

📔 Reference

[이것이 취업을 위한 코딩 테스트다 - 나동빈]

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체