[99클럽 코테 스터디 35일차 TIL] 게임 맵 최단거리 - Java [자바][프로그래머스]

 

 

📜 문제 내용

 

🤔 과정

• 최단거리를 찾는 문제로, BFS와 boolean형의 방문 배열을 활용하면 된다. 
• Delta 배열과 Queue, 경계 범위 조건을 활용해 문제를 풀이. 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static int[] dr = {1, -1, 0, 0};
    public static int[] dc = {0, 0, 1, -1};
    
    public int solution(int[][] maps) {
        int n = maps.length;  // 행
        int m = maps[0].length; // 열
        
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<>();
        
        // {행, 열, 이동횟수}
        queue.add(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0];
            int c = current[1];
            int dist = current[2];
            
            // 목표 지점 도달 시 이동횟수 반환
            if (r == n - 1 && c == m - 1) {
                return dist;
            }
            
            // 4방 탐색
            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                
                if (boundaryCheck(nr, nc, n, m) && !visited[nr][nc] && maps[nr][nc] != 0) {
                    queue.add(new int[]{nr, nc, dist + 1});
                    visited[nr][nc] = true;
                }
            }
        }
        
        // 목표 지점 도달이 불가능하다면 -1 반환
        return -1; 
    }
    
    // 경계 범위 확인
    public boolean boundaryCheck(int r, int c, int n, int m) {
        return r >= 0 && c >= 0 && r < n && c < m;
    }
}

 

🔗 문제 링크

• 프로그래머스 - 게임 맵 최단거리 (링크) 

프로그래머스