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

#문제

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

코딩테스트 연습 - 게임 맵 최단거리

#풀이

BFS 알고리즘으로 도착 지점 도달까지의 최단 거리를 구하여 리턴하였다. 

 

#소스코드

import java.util.*;
class Solution {    
    public int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public int[][] map;
    public boolean [][] visit;
    public int m = 0, n = 0;
    
    public int bfs(int x, int y){
        int cnt = 0;
        boolean isArrive = false;
        this.n = map.length; 
        this.m = map[0].length;
        this.visit = new boolean[n][m];
        
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(x);
        que.offer(y);
        que.offer(1);
        visit[x][y] = true;
        
        while(!que.isEmpty()){
            int i = que.poll();
            int j = que.poll();
            int c = que.poll();
            if(i == n-1 && j == m-1){
                cnt = c;
                isArrive = true;
                break;
            }
            for(int[] d : dir){
                int nx = i + d[0];
                int ny = j + d[1];
                int nc = c + 1;
                if(isValid(nx, ny)){
                    que.offer(nx);
                    que.offer(ny);
                    que.offer(nc);
                    visit[nx][ny] = true;
                }
            }
        }
        if(isArrive) return cnt;
        return -1;
    }
    
    public boolean isValid(int x, int y){
        if(x < 0 || y < 0 || x >= n || y >= m || visit[x][y] || map[x][y] == 0) return false;
        return true;
    }
    
    public int solution(int[][] maps) {
        this.map = maps;        
        return bfs(0, 0);
    }
}