프로그래머스 | LV.2 게임 맵 최단거리 - BFS, 다익스트라 문풀 (Java)

⬛ 프로그래머스 | LV.2 게임 맵 최단거리 - BFS, 다익스트라 문풀 

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

프로그래머스

문제 설명 1

문제 설명 2

---

💚문제 접근 방식

• 이 게임은(0,0) → (N-1, N-1) 위치까지 한 정점에서 다른 정점까지 최소 칸을 사용하여 먼저 도착하면 이기는 게임이다.
• 한 정점에서 다른 정점까지 최단경로로 가는 알고리즘  ‘다익스트라’를 활용해도 되고, BFS도 인접 정점을 먼저 방문하는 알고리즘이기 때문에 BFS를 활용하여 인접한 정점을 우선으로 선점하면서 상태 팀 진영으로 향하다 보면 최소값으로 도착할 수 있다.

---

💚 BFS 로 문제 풀기

• BFS는 기본적으로 인접 정점을 먼저 방문한다. 그러니 여러 길이 있어도 현재 좌표에서 계속해서 더 가까운 정점으로만 쭉 뻗어가므로 결과적으로는 목표 지점에 최단 거리로 도착해있을 것이다. 
• 입력으로 들어온 maps[][]는 갈 수 있는 곳을 1, 없는 곳을 0 으로 세팅해둔 배열이기 때문에 이 값을 활용해서 (0,0) → (N-1, N-1) 까지 직전 방문 정점 + 1 값으로 갱신해가며 진행하다보면 상대팀 진영에 도착할 수 있다.
• 물론 벽에 가로막혀서 못 가는 경우도 있기 때문에 이런 경우는 BFS로 순회를 다 했는데도 불구하고 여전히 maps[N-1][N-1] 값이 1이라면 도달 못했다는 의미이므로 -1을 리턴하고, 그게 아니라면 maps[N-1][N-1]값을 그대로 리턴하여 정답을 구할 수 있다.

풀이 부연 설명

import java.util.*;

class Solution {
    static boolean[][] visited;
    //4방향 
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    
    //BFS
    static int BFS(int x, int y, int[][] maps){
        Queue<int[]> Q = new LinkedList<>();
        Q.offer(new int[] {x, y});
        visited[x][y] = true;
        
        while(!Q.isEmpty()){
            int[] cur = Q.poll();
            if(cur[0] == maps.length-1 && cur[1] == maps[0].length-1) return maps[cur[0]][cur[1]];
            
            for(int k=0; k<4; k++){
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                
                if(nx <0 || ny <0 || nx >= maps.length || ny >= maps[0].length || maps[nx][ny]==0) continue;
                
                if(!visited[nx][ny]) {
                    maps[nx][ny] = maps[cur[0]][cur[1]] + 1;
                    Q.offer(new int[] {nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        return maps[maps.length-1][maps[0].length -1];
    }
    
    //솔루션
    public int solution(int[][] maps) {
        
        visited = new boolean[maps.length][maps[0].length];
        
        int answer = BFS(0, 0, maps);
        if(answer == 1){
            return -1;
        }
          
        return answer;
    }
}

---

💚 다익스트라로 문제 풀기

• (0,0) → (N-1, N-1) 로 한 정점에서 다른 정점으로의 최단 거리를 구하는 문제이므로 다익스트라로도 해결할 수 있는 문제이다.
• distance[][] 배열은 최초에 Integer.MAX_VALUE값으로 초기화해두고, 시작정점만 세팅해준 뒤 pQ를 활용하여 계속해서 거리 더 적은 값을 우선으로 방문하도록 거리 값을 갱신해준다.
• 만약 dijkstra() 함수가 리턴된 시점에서도 여전히 Integer.MAX_VALUE라면 방문 못했단 소리이므로 -1을 리턴하고, 그게 아니라면 담긴 값을 리턴하면 된다.

[PriotiryQueue 정렬 조건 반드시 명시하기]

• 마지막에 계속 PriorityQueue에서 오류가 나서 헤맸는데 오류 원인이 정렬 기준을 재정의 안해둬서였다.
• 객체를 담을거면 객체에 대한 정렬 기준을, int[]를 담을 거면 무엇을 기준으로 재정렬 할 건지 정의해줘야 한다.

//우선순위 큐 정렬 기준 = 거리값 오름차순
PriorityQueue<int[]> pQ= new PriorityQueue<>((a, b) -> a[2]-b[2]);

• 어쨋든 해결 !

import java.util.*;

class Solution {
    static int N, M;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int[][] distance;
    //다익스트라 
    static int dijkstra(int x, int y, int[][] maps){
        //우선순위 큐 정렬 기준 = 거리값 오름차순
        PriorityQueue<int[]> pQ= new PriorityQueue<>((a, b) -> a[2]-b[2]);
        distance = new int[N][M];
        
        for(int i=0; i<N; i++) Arrays.fill(distance[i], Integer.MAX_VALUE);
        
        distance[x][y] = 1; //시작 정점 거리 1 
        pQ.offer(new int[]{x, y, distance[x][y]});
        
        while(!pQ.isEmpty()){
            int[] cur = pQ.poll();
            if(cur[0] == N-1 && cur[1] == M-1) return distance[N-1][M-1];
            
            for(int k=0; k<4; k++){
                int nx = cur[0] + dx[k];
                int ny = cur[1] + dy[k];
                if(nx <0 || ny <0 || nx >= N || ny >=M || maps[nx][ny] == 0) continue;
                if(distance[nx][ny] > distance[cur[0]][cur[1]] + 1){
                    distance[nx][ny] = distance[cur[0]][cur[1]] + 1;
                    pQ.offer(new int[] {nx, ny, distance[nx][ny]});
                }
            }
        }
        return distance[N-1][M-1];
    }
    
    public int solution(int[][] maps) {
        
        N = maps.length;
        M = maps[0].length;
 
        int answer = dijkstra(0, 0, maps);
        
        if(answer == Integer.MAX_VALUE){ //도달 못했다는 거니까
            return -1;
        }
        
        return answer;
    }
}

---

예전에는 BFS로 풀었던 적 있는 문제 이번에는 BFS와 다익스트라로 모두 풀어봤다.ㅎㅎ

프로그래머스 | LV.2 게임 맵 최단 거리 - BFS 풀이