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

문제

프로그래머스

 

풀이

2차원 배열 내 0,0 에서 N-1,M-1 까지 도달하는데 걸리는 최단시간 찾는 문제입니다.

최단거리를 구하는 방법은 총 3가지가 있으며, 3가지 방법 모두 구현해보았습니다.

(아래의 링크에 최단거리를 구하는 방법에 대해 간단히 적어놓았습니다.)

BFS와 다익스트라

 

코드

1. int[]를 이용해 다음으로 갈 노드위치와 가중치를 넘겨주는 방식

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

class Solution {
    static int N, M, ans;
    static boolean[][] v;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int[][] map;
    public int solution(int[][] maps) {
        ans = -1;
        map = maps;
        N = map.length;
        M = map[0].length;
        v = new boolean[N][M];
        v[0][0] = true;
        
        BFS(0, 0);
        return ans;
    }
    
    private static void BFS(int r, int c) {
        Queue<int []> q = new ArrayDeque<>();
        q.offer(new int[]{r, c, 1});

        while(!q.isEmpty()){
            int tmp[] = q.poll();
            r = tmp[0];
            c = tmp[1];
            int cnt = tmp[2];

            if(r == N -1 && c == M -1){
                ans = cnt;
                break;
            }

            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];

                if (nr >= 0 && nr < N && nc >= 0 && nc < M) {
                    if (map[nr][nc] == 1 && !v[nr][nc]) {
                        v[nr][nc] = true;
                        q.offer(new int[]{nr, nc, cnt+1});
                    }
                }
            }
        }
    }
}

 

2. 방문 배열을 int로 두고 최단거리 저장

import java.util.*;

class Solution {
    static int N, M;
    static int[][] arr, v;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public int solution(int[][] maps) {
        N = maps.length;
        M = maps[0].length;
        arr = maps;
        
        v = new int[N][M];
        
        for(int i = 0 ; i < N ; i ++)
            Arrays.fill(v[i], 1 << 20);
        
        return bfs();
    }
    
    public int bfs(){
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});
        v[0][0] = 1;
        int ans = 1 << 20;
        
        while(!q.isEmpty()){
            int[] cur = q.poll();
            
            if(cur[0] == N-1 && cur[1] == M-1){
                ans = Math.min(ans, v[N-1][M-1]);
                continue;
            }
            
            for(int d = 0 ; d < 4 ; d ++){
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];
                
                // 유효범위를 벗어났거나, 벽이거나, 이전까지 왔던 거리보다 많을 경우 pass
                if(!isValid(nr, nc) || arr[nr][nc] == 0 || v[nr][nc] <= v[cur[0]][cur[1]] + 1)
                    continue;
                
                v[nr][nc] = v[cur[0]][cur[1]] + 1;
                q.offer(new int[]{nr, nc});
            }
        }
        
        return ans == 1 << 20 ? -1 : ans;
    }
    
    public boolean isValid(int nr, int nc){
        return (nr>=0 && nr<N && nc>=0 && nc<M);
    }
}

 

3. 큐 사이즈만큼 순회하며 depth별 탐색

import java.util.*;

class Solution {
    static int N, M;
    static int[][] arr;
    static boolean[][] v;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public int solution(int[][] maps) {
        N = maps.length;
        M = maps[0].length;
        arr = maps;
        
        v = new boolean[N][M];
        
        return bfs();
    }
    
    public int bfs(){
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0});
        v[0][0] = true;
        int time = 1;
        
        while(!q.isEmpty()){
            int qSize = q.size();
            for(int i = 0 ; i < qSize ; i ++){
                
                int[] cur = q.poll();

                if(cur[0] == N-1 && cur[1] == M-1){
                    return time;
                }

                for(int d = 0 ; d < 4 ; d ++){
                    int nr = cur[0] + dr[d];
                    int nc = cur[1] + dc[d];

                    // 유효범위를 벗어났거나, 벽이거나, 이전까지 왔던 거리보다 많을 경우 pass
                    if(!isValid(nr, nc) || arr[nr][nc] == 0 || v[nr][nc])
                        continue;

                    v[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
            
            time ++;
        }
        
        return -1;
    }
    
    public boolean isValid(int nr, int nc){
        return (nr>=0 && nr<N && nc>=0 && nc<M);
    }
}