[level2] 프로그래머스 - 게임 맵 최단거리(JAVA)

 

 

[ 풀이 방법 ]

- BFS를 연습하기에 좋은 문제였던 것 같다.

 

 

- maps의 방문여부를 저장할 isVisited를 만들고, 
   방문하지 않은 좌표이면서, maps[r][c]의 값이 1인 곳으로 나아가면서 칸의 수(answer)를 세면 된다.

 

 

- (0, 0)에서 사방으로 나아가면서 만약 (n, m)에 도달하면 true를 리턴하고,
   사방으로 들릴 수 있는 모든 점을 다 들렸지만 (n, m)에는 가지 못 했다면 false를 리턴한다.

 

 

- bfs결과가 true면 (n, m)까지의 칸의 수인 answer을 리턴하고,
   false면 -1을 리턴한다.

 

 

 

 

[ 전체 코드 ]

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    static int answer, R, C;
    static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
    static boolean[][] isVisited;

    public int solution(int[][] maps) {
        R = maps.length;
        C = maps[0].length;
        isVisited = new boolean[R][C];

        return bfs(maps) ? answer : -1;
    }

    private static boolean bfs(int[][] maps) {
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[] { 0, 0 });
        isVisited[0][0] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            answer++;
            while (--size >= 0) {
                int[] q = queue.poll();

                if (q[0] == R - 1 && q[1] == C - 1)
                    return true;

                for (int i = 0; i < 4; i++) {
                    int nr = q[0] + dr[i];
                    int nc = q[1] + dc[i];

                    if (nr < 0 || nc < 0 || nr >= R || nc >= C || isVisited[nr][nc] || maps[nr][nc] == 0)
                        continue;

                    isVisited[nr][nc] = true;
                    queue.offer(new int[] { nr, nc });
                }
            }
        }

        return false;
    }
}