[프로그래머스 Lv2][JAVA] 게임 맵 최단거리

❓문제설명

게임 맵 최단거리

프로그래머스

---

🔍문제해석

어떤걸 풀어야 할까?

• mxn의 이차원 배열에서 상대방 위치까지 도달하는 데에 최소거리를 구하자.
• 나의 시작 위치는 0,0 ,  상대방 위치는 m-1,n-1 로 고정되어있다.
• 상하좌우 방향으로 이동할 수 있으며 한칸 이동시 거리가 +1 된다.
• mxn의 이차원 배열에서 값이 1인 칸만 이동 가능하다. 0은 장애물이다.

---

🧐문제풀이

• 문제 풀이 구상

이동 가능한 지점과 현재 거리를 queue에 담는다. 

queue에서 하나 poll()하여 해당 지점에서 상하좌우로 예상 이동 지점을 계산해보고 그 지점이 이동가능한 칸이면 queue에 담고 거리도 +1 해준다.

queue가 빌때까지 혹은 목표지점에 도달했을때까지 위 계산을 계속한다.

• 알고리즘 선택

지문에 최단거리!! 얘기가 나오면 일단 BFS로 생각하고 있다.

---

！제출코드

1. 왔던 길로 되돌아 가지 않기 위해 방문여부를 표시하는 배열을 만들어준다.
2. 처음 지점을 넣어준다. 
3. 목표에 도달하면 그동안 계산해 왔던 거리를 return한다.
4. 상하좌우 네 방향을 계산해보고 그 지점이 지도 안에 있는지, 장애물은 아닌지, 방문한적은 없는지 체크한다.
5. 이동 가능한 지점이면 거리 + 1하여 다시 Queue에 넣어주고, 방문표시를 한다.

import java.util.*;

class Solution {

   public static int solution(int[][] maps) {
   
        int m = maps.length;
        int n = maps[0].length;
        // (1)
        int[][] visit = new int[m][n];

        int answer = bfs(maps,visit);
        return answer;
    }
    
    public static int bfs(int[][] maps, int [][] visit) {
    
        int [] dy = {1,-1,0,0};
        int [] dx = {0,0,-1,1};
        Queue<int[]> queue = new LinkedList<>();
        
        // (2)
        int [] start = new int[]{0,0,1};
        visit[start[0]][start[1]] = 1;
        queue.offer(start);
        
        while (!queue.isEmpty()) {
        
           int size  =  queue.size();
           
           for(int i = 0; i < size; i++) {
           
               int [] point = queue.poll();
               // (3)
               if(point[0] == maps.length -1 && point[1] == maps[0].length -1 ){
                    return point[2];
               }

               for(int j = 0; j < 4; j++) {
               
               	   // (4)
                   int newY = point[0] + dx[j];
                   int newX = point[1] + dy[j];
                   
                   if(newY > -1 && newY < maps.length
                           && newX > -1 && newX < maps[0].length
                           && maps[newY][newX] == 1
                           && visit[newY][newX] == 0) {

                       // (5)
                       queue.offer(new int[]{newY, newX,point[2]+1});
                       visit[newY][newX] = 1;
                   }
               }
           }
        }
           return -1;
    }
}