프로그래머스 1844: 게임 맵 최단거리 [JAVA]

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

프로그래머스

 

[난이도]

- level 2

 

[알고리즘]

- BFS

 

[코드]

import java.util.*;

class Solution {
    static int answer = -1; // 우측하단에 도착하지못할경우 -1출력
    public int solution(int[][] maps) {
        bfs(maps);
        
        return answer;
    }
    static void bfs(int[][] maps){
        int n = maps.length;
        int m = maps[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;
        int[] dx = {-1, 1, 0, 0}; // 4방탐색
        int[] dy = {0, 0, -1, 1};
        while(!queue.isEmpty()){
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            if(x == n-1 && y == m-1){ // 우측하단에 도착했을 경우
                answer = count;
                return;
            }
            for(int i=0;i<4;i++) { // 4방탐색
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx>=0&&nx<n&&ny>=0&&ny<m){ // 지도 내에 있을 경우
                    if(!visited[nx][ny] && maps[nx][ny] == 1){ // 방문한 적 없고, 벽이 아닐경우
                        queue.offer(new int[]{nx, ny, count+1});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
        return;
    }
}

[풀이]

일반적인 미로찾기 BFS 알고리즘이다. 

 

큐에 x좌표, y좌표, 밟은블럭의 수를 담아준다.

queue.offer(new int[]{x, y, count});