프로그래머스 lv2 - 게임 맵 최단거리 (자바)

문제

---

프로그래머스 lv2 - 게임 맵 최단거리

풀이

---

매우 기초적인 bfs 최단거리 문제

bfs를 이용해서 최단 거리를 visited[][] 배열에 갱신한다.
최종 목적지인 visited[n][m] 에 들어 있는 값이 최단 거리가 된다.

코드

---

import java.util.*;
class Solution {
    static int[] dy = {-1,0,1,0};
    static int[] dx = {0,1,0,-1};
    public int solution(int[][] maps) {
        int n = maps.length, m = maps[0].length; // 세로, 가로
        int[][] visited = new int[n][m];
           Queue<int[]> q = new LinkedList<>();

        q.add(new int[]{0, 0});
        visited[0][0] = 1;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m || maps[ny][nx] == 0) continue;
                if (visited[ny][nx] > 0) continue;
                visited[ny][nx] = visited[cur[0]][cur[1]] + 1;
                q.add(new int[]{ny, nx});
            }
        }

        return visited[n - 1][m - 1] > 0 ? visited[n - 1][m - 1] : -1;
    }
}