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

게임 맵 최단거리

풀이

• 단순 최단거리 찾는 bfs
• 근데 ide 없이 풀려니까 상당히,,,실수가 많고 오래걸림,,,
• 연습이 많이 필요할 거 같다!!

코드

import java.util.*;
import java.io.*;
class Solution {
    static int[] dx ={-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] maps;
    static boolean[][] visited;
    static int N,M;
    static int answer = Integer.MAX_VALUE;
    public int solution(int[][] maps) {
        //캐릭터가 상대 팀 진영에 도착하기 위해 지나가야하는 칸의 개수의 최소값!
        //0은 벽이 있는자리, 1은 벽이 없는 자리
        //(1,1)에서 (n,m) 으로 이동,
        //동서남북 이동 가능
        this.maps = maps;
        N = maps.length;
        M = maps[0].length;
        visited = new boolean[N][M];
        bfs(0,0,1);
        
        if(answer == Integer.MAX_VALUE) answer = -1;
        return answer;
    }
    
    public void bfs(int i, int j, int cnt){
        visited[i][j]  = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i,j,cnt});
        
        while(!queue.isEmpty()){
            int[] now = queue.poll();
            int x = now[0];
            int y = now[1];
            int c = now[2];
            
            
            if(x==N-1 && y==M-1){
                //도착한 경우
                answer = Math.min(answer,c);
            }
            else{
                for(int m=0;m<4;m++){
                    int nx = x+dx[m];
                    int ny = y+dy[m];
                    if(nx>=0 && nx<N && ny>=0 && ny<M && maps[nx][ny]==1 && !visited[nx][ny]){
                        visited[nx][ny]=true;
                        queue.add(new int[]{nx,ny,c+1});
                    }
                }
            }
            
            
        }
        
    }
    
}