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

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

프로그래머스

 

 

Idea

BFS는 가장 처음 찾은 답이 최단 거리를 보장하므로 아래와 같은 코드로 작성했다.

 

 

Code

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        
        return bfs(maps, n, m);
    }
    
    private int bfs(int[][] maps, int n, int m) {
        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        
        boolean[][] visited = new boolean[n][m];        
        Queue<int[]> q = new LinkedList<>();
        
        q.offer(new int[]{0, 0});
        visited[0][0] = true;
        maps[0][0] = 1;
        
        while(!q.isEmpty()) {
            int[] current = q.poll();
            int cx = current[0];
            int cy = current[1];
            
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                    maps[nx][ny] = maps[cx][cy] + 1;
                }
            }
            
            if (cx == n - 1 && cy == m - 1) {
                return maps[cx][cy];
                // 목표 지점인 (n - 1, m - 1)에 도달했을 때 그 위치는 최단 거리롤 탐색했을 때 도달한 위치이다.
                // bfs에서는 처음 도달한 위치가 최단거리로 보장되므로 maps[cx][cy]는 목표 지점까지의 최단 거리를 의미하게 된다.
            }
        }
        return -1;
    }
}