[프로그래머스] Lv2. 게임 맵 최단거리 (BFS)

프로그래머스

문제 파악

정말 단순히 벽에 둘러싸져있는 길에서 목적지까지 최단거리를 구하는 문제

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

 

입출력 예

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

---

접근 방법

단순히 BFS 탐색으로 최단거리를 구하면 되는 문제!!

 

쉽게 4방향 이동하면서 목적지까지의 최단거리를 구하는 단순한 문제여서 BFS로 풀면 되겠다는 생각을 했다.

 

거리가 1부터 시작하는 이유는 자기 자신의 칸도 거리로 간주해서 1로 시작해야 올바른 정답이 나온다.

---

코드 구현

import java.util.*;

class Solution {
    static int n;
    static int m;
    public int solution(int[][] maps) {
        // BFS로 최단거리 구하기
        n = maps.length;
        m = maps[0].length;

        int[] dr = {-1,1,0,0};
        int[] dc = {0,0,-1,1};


        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        // 시작점 예약 (0,0 , 거리 0)
        queue.offer(new int[]{0,0,1});
        visited[0][0] = true;

        while(!queue.isEmpty()){
            // 현재 노드 방문
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            // if 도착지 도달하면 return dist
            if(r == n-1 && c == m-1) return dist;

            // 다음 노드 예약
            for(int i=0; i <4; i++){
                int nr = r + dr[i];
                int nc = c + dc[i];

                if(isValid(nr, nc)){
                    if(maps[nr][nc] == 1 && !visited[nr][nc]){
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc, dist + 1});
                    }
                }
            }
        }
        return -1;
    }
    public boolean isValid(int r, int c){
        return (r >= 0 && r < n && c >= 0 && c < m);
    }
}