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

https://school.programmers.co.kr/learn/courses/30/lessons/1844#

프로그래머스

import java.util.*;
import java.io.*;

class Solution {
    
    static class Point{
        int x;
        int y;
        
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[][] visited;
    static int N, M;
    static Queue<Point> queue;
    static int answer;
    
    
    
    static boolean isIn(int x, int y){
        if(x<0||x>N-1||y<0||y>M-1) return false;
        return true;
    }
    
    static void bfs(int[][] maps, int x, int y){
        queue = new LinkedList<>();
        
        queue.add(new Point(x,y));
        
        visited[x][y] = 1;
        
        
        while(!queue.isEmpty()){
            Point tmp = queue.poll();
            
            for(int d=0;d<4;d++){
                int nx = tmp.x+dx[d];
                int ny = tmp.y+dy[d];

                if(!isIn(nx,ny)) continue;
                if(visited[nx][ny]==0&&maps[nx][ny]==1){
                    visited[nx][ny]=visited[tmp.x][tmp.y]+1;
                    queue.add(new Point(nx,ny));
                }
            }
        }
        
    }
    
    
    public int solution(int[][] maps) {
        answer = 0;
        N = maps.length;
        M = maps[0].length;

        visited = new int[N][M];
        
        bfs(maps, 0, 0);
        answer = visited[N-1][M-1];
        
        if(answer==0) answer = -1;
        
        
        return answer;
    }
}

기본적인 bfs 문제이다. 방문체크를 해줌과 동시에 거리를 기록해준다.