게임 맵 최단거리_bfs

사용 알고리즘: bfs

사용 언어: java

 

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

class Solution {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static boolean[][] visited;
    static int answer = Integer.MAX_VALUE;
    
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        visited = new boolean[n][m];
        visited[0][0] = true;
        fs(0,0, maps, 1, n,m);
        
        // int answer = 0;
        return answer==Integer.MAX_VALUE ? -1 : answer;
    }
    
    public void fs(int x, int y, int[][] maps, int cnt, int n, int m){
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {x,y, cnt});
        
        while(!q.isEmpty()) {
            int[] p = q.poll();
            for(int d=0; d<4; d++) {
                int nx = p[0] + dx[d];
                int ny = p[1] + dy[d];
                
                if(nx==n-1 && ny==m-1){
                    answer = Math.min(answer, p[2]+1); //조심
                    return;
                }
                
                if(nx>=0 && nx<n && ny>=0 && ny<m && maps[nx][ny]==1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.offer(new int[] {nx,ny, p[2]+1}); //조심
                }
            }
        }
        
        return;
    }
}

 

이슈:

길이 있는 맵에서 자꾸 2가 답이 되어 문제 -> p[2]를 사용하지 않고 cnt를 사용하여서 계속 1+1만 하고 있었음. 변수 조심!