[프로그래머스 lv.2] 게임 맵 최단거리

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

프로그래머스

---

📝 문제 설명

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길의 거리를 반환하면 된다.

가장 빠른 길의 칸 수를 계산하면 되며 적 팀의 진영까지 도달할 방법이 없으면 -1을 반환하면 된다.

✨ 제출 코드

import java.util.*;

class Solution {
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    
    static int n;
    static int m;
    
    static int [][] result;
    
    public int solution(int[][] maps) {        
        n = maps.length;
        m = maps[0].length;
    
        result = new int [n][m];
        
        bfs(0,0,maps);
        
        int answer = -1;
        
        if(result[n-1][m-1] !=0) answer = result[n-1][m-1] + 1;
        
        return answer;
    }
    
    public static void bfs(int x, int y, int [][] maps){
        Queue<int []> q = new LinkedList<>();
        q.offer(new int [] {x,y});
        
        while(!q.isEmpty()){
            int [] cur = q.poll();
            
            int curX = cur[0];
            int curY = cur[1];
            
            for(int i = 0; i < 4; i++){
                int nx = curX + dx[i];
                int ny = curY + dy[i];
                
                if(nx>=0 && nx<n && ny >=0 && ny<m && maps[nx][ny] == 1){
                    q.offer(new int[] {nx,ny});
                    maps[nx][ny] = 0;
                    result[nx][ny] = result[curX][curY] + 1;
                }
            }
        }
    }
}

 

✌️ 코드 설명

먼저 최소 거리를 구해야 하기 때문에 bfs를 이용했다. 일단 상하좌우 배열과 n, m과 result배열을 static변수로 선언했다.

result배열에는 각 칸까지 이동하는데 걸리는 칸 수를 저장해 줄 거다.

bfs는 0,0부터 시작하기 위해 x, y좌표와 maps를 같이 넘겨주었다.

bfs에서는 이제 1인 칸들을 탐색할 거다. 캐릭터는 1인 칸만 이동할 수 있기 때문이다.

이동하면서 지나온 길은 0으로 바꿔주고 result배열에는 이전에 있던 칸의 값에 +1을 해준다.

문제에서는 0,0부터 1칸을 간 거라고 생각하기 때문에 마지막에 반환할 때는 마지막 칸의 값에 +1을 반환해 주었다.