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

문제

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

---

문제 파악

• maps의 크기는 n x m
• maps의 값이 1인 공간으로만 갈 수 있음
• 최단거리 → bfs 사용

---

접근 방법

1. 시작점 초기화, 방문처리
2. 상하좌우로 움직이게 할 수 있는 행, 열 배열 각각 생성
3. while(q가 빌때 까지) 하나씩 뽑음, 만약 뽑은 값이 도착점이면 dist return
4. 상하좌우 배열을 하나씩 더하며 주변 노드 탐색
5. 조건에 맞는 노드가 있으면 방문처리, 다시 큐에 넣어줌

---

코드 구현

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> q = new ArrayDeque<>();
        
        q.add(new int[]{0, 0, 1});
        visited[0][0] = true;
        
        int[] dr = {0, 1, 0, -1};
        int[] dc = {-1, 0, 1, 0};
        
        while(!q.isEmpty()){
            int[] cur = q.remove();
            int r = cur[0], c = cur[1], dist = cur[2];
            
            if(r == n - 1 && c == m -1)
                return dist;
            
            for(int d = 0; d < 4; d++){
                int nr = r + dr[d], nc = c + dc[d];
                
                if(nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && maps[nr][nc] ==1 ){
                    visited[nr][nc] = true;
                    q.add(new int[]{nr, nc, dist +1});
                }
            }
        }
        return -1;
    }
}