Programmers - 게임 맵 최단 거리 with JAVA (V)

 

 

전형적인 DFS/BFS 문제이긴 하나 조건 설정에 따라 효율성이 달라진다. 그 부분을 기록해보고자 한다.

 

 

 

사용 : BFS

효율성 증가 : 방문처리, 목표지 방문시 종료 처리

 

 

 

로직 및 코드

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(maps[i][j] == 1){
                    maps[i][j] = (int)1e9;
                }
                if(maps[i][j] == 0){
                    maps[i][j] = -1;
                }
            }
        }
        boolean[][] visited = new boolean[n][m];
        maps[0][0] = 0;
        PriorityQueue<List<Integer>> check 
            = new PriorityQueue<>(Comparator.comparing(arr -> arr.get(0)));
        check.add(Arrays.asList(0, 0, 0));
        while(check.size() != 0){
            List<Integer> now = check.poll();
            int cost = now.get(0);
            int x = now.get(1);
            int y = now.get(2);
            if(x == n-1 && y == m-1){
                return cost+1;
            }
            if(visited[x][y]){
                continue;
            }
            visited[x][y] = true;
            for(int i=0; i<4; i++){
                int next_x = x + dx[i];
                int next_y = y + dy[i];
                int next_cost = cost + 1;
                if(next_x < 0 | next_x >= n | next_y < 0 | next_y >= m){
                    continue;
                }
                if(maps[next_x][next_y] == -1){
                    continue;
                }
                if(maps[next_x][next_y] < next_cost){
                    continue;
                }
                maps[next_x][next_y] = next_cost;
                check.add(Arrays.asList(next_cost, next_x, next_y));
            }
        }
        if(maps[n-1][m-1] >100000){
            return -1;
        }
        return maps[n-1][m-1]+1;
    }
}