[프로그래머스 / Level2] 게임 맵 최단거리 (Java)

문제 보기

사용한 것

• (0, 0) ~ (N - 1, M - 1) 최단거리를 구하기 위한 BFS

풀이 방법

• q의 원소로 {x 좌표, y 좌표, 거리} int 배열를 사용하여 풀이

코드

class Solution {

    int N;
    int M;
    int[][] maps;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};

    public int solution(int[][] maps) {
        N = maps.length;
        M = maps[0].length;
        this.maps = maps;

        return bfs();
    }

    int bfs() {
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> q = new LinkedList<>();
        visited[0][0] = true;
        q.offer(new int[]{0, 0, 1});

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            if (cur[0] == N - 1 && cur[1] == M - 1) {
                return cur[2];
            }

            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if (!isOOB(nx, ny) && !visited[nx][ny] && maps[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    q.offer(new int[]{nx, ny, cur[2] + 1});
                }
            }
        }

        return -1;
    }

    boolean isOOB(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= M) {
            return true;
        }

        return false;
    }
}