[lv2] 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

 

최단 거리 이므로 bfs 사용

출발점의 depth가 0이 아닌 1임에 주의

 

import java.util.*;

class Solution {
    int[][] maps;
    int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
    boolean[][] vst;
    Queue<int[]> q = new ArrayDeque<>();


    int solve() {

        int R = maps.length;
        int C = maps[0].length;
        int ER = R - 1;
        int EC = C - 1;

        vst = new boolean[R][C];

        q.offer(new int[]{0, 0, 1});
        vst[0][0] = true;

        while(!q.isEmpty()) {
            int[] info = q.poll();
            int r = info[0];
            int c = info[1];
            int dep = info[2];

            if(r == ER && c == EC)
                return dep;

            for(int i=0; i<4; i++) {
                int tr = r + dr[i];
                int tc = c + dc[i];

                if(tr >= 0 && tr < R && tc >= 0 && tc < C && !vst[tr][tc] && maps[tr][tc] != 0) {
                    vst[tr][tc] = true;
                    q.offer(new int[]{tr, tc, dep + 1});
                }
            }
        }

        return -1;
    }

    public int solution(int[][] maps) {
        this.maps = maps;

        return solve();
    }
}