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

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java

프로그래머스

---

이 문제는 전형적인 bfs 문제가 아닐까 싶다.

방문할때마다 이전 방문지 값에 +1을 해주고 최하단에 도착했을 때 값을 반환해준다.

최하단에 이르지 못하는 경우에는 -1을 반환해준다.

 

대충 이러한 그림을 상상할 수 있다.

이 경우 최하단에 도착했을 때 11이므로 11을 그대로 반환해주면 된다.

 

이를 구현한 코드는 아래와 같다.

import java.util.*;
class Solution {
    public int solution(int[][] maps) {
        int answer = -1;
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        
        while(!queue.isEmpty()){
            int[] current = queue.poll();
            int n = current[0];
            int m = current[1];
            if(n == maps.length - 1 && m == maps[0].length-1){
                return maps[n][m];
            }
            
            for(int i = 0; i < 4; i++){
                int nx = n + dx[i];
                int my = m + dy[i];
                if(nx >= 0 && my >= 0 && nx < maps.length && my < maps[0].length
                   && maps[nx][my] == 1){
                    maps[nx][my] = maps[n][m] + 1;
                    queue.add(new int[]{nx, my});
                }
            }
        }
        return answer;
    }   
}

처음에 n,m을 Node 클래스에 생성해서 큐에 넣어줬는데 int[]{} 배열로 사용하면 속도가 더 빠르다!~