[프로그래머스][Java] Lv.2 게임 맵 최단거리

이 방법으로 가는 것이 최단거리로 총 11칸을 가야 한다.

---

문제 분석

 

최솟값을 return 하는 것이기 때문에 BFS를 활용해야겠다고 생각하고 구현하였다.

---

풀이과정

1. bfs를 구현하여 시작점인 (0,0)을 넘겨준다.
2. 벽이 없는 자리를 1로 나타내기 때문에,
   방문했다는 것을 나타내기 위해 시작점을 2로 만들고 bfs를 진행한다.
3. Queue를 사용하여 현재 칸의 상하좌우를 확인하고,
   벽이 없는 자리이고 아직 방문하지 않은 칸이라면 해당 칸의 x,y좌표를 Queue에 넣습니다.
4. 현재 칸의 상하좌우 조사가 끝나면, Queue에 넣은 순서대로 다음 칸을 차례대로 방문하며
   map의 해당 칸에 (이전 방문했던 순서+1)을 저장한다.
5. 도착지점인 (n-1,m-1)에 도착하면 bfs 를 종료하고, map[n-1,m-1]-1값을 return 한다.
    ** 처음 시작지점을 2로 시작했기 때문에 마지막에 -1을 해준다.
6. 만약 Queue가 비워질 때까지 도착지점에 도달하지 못한다면, bfs를 종료하고 -1을 return 한다.

---

전체 코드

import java.util.*;
class Solution {
    static int[][] map;
    static int[] dx = {0,1,0,-1}; //방향
    static int[] dy = {1,0,-1,0};
    static int n,m;
    public int solution(int[][] maps) {
        
        map = maps;
        //도착지점
        n = map.length;
        m = map[0].length;
        
        int answer = bfs(0,0);
        
        return answer;
    }
    private static int bfs(int x,int y){
        
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x,y});
        map[x][y]++; //지나온 길을 기억하기 위해 첫 시작점을 2로 한다.
        
        while(!q.isEmpty()){
            int[] now = q.poll();
            //System.out.print("("+now[0]+","+now[1]+") ");
            
            if(now[0]==n-1 && now[1]==m-1)
                return map[n-1][m-1]-1; //처음 시작을 2로 해줬기 때문에 -1한 값을 반환함.
            
            for(int i=0;i<4;i++){
                x=now[0]+dx[i];//x좌표
                y=now[1]+dy[i];//y좌표
                
                //상하좌우 방향으로 움직였을 때 n*m배열 안에 있고,
                //다음 조사할 값이 현재 칸의 idx 보다 작거나 같을 때만 조사한다.
                if(x>=0 && x<n && y>=0 && y<m && map[x][y]==1){
                    q.add(new int[]{x,y});
                    map[x][y] = map[now[0]][now[1]]+1;
                }
            }
            //System.out.println(map[now[0]][now[1]]);
        }
        return -1; //도착지점에 도달하지 못한 경우.
    }
}