[프로그래머스] 게임 맵 최단거리 - 자바

프로그래머스 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=java 

프로그래머스

아이디어

• 최단거리이기 때문에 BFS 알고리즘 사용
• 캐릭터가 한칸 갈때마다 기존의 위치에서 +1을 해주면 총 이동한 거리가 된다
• 이동가능한 좌표(상, 하, 좌, 우) 에 대해서 벽인 경우에는 넘어가고 벽이 아닌경우에는 진행한다
• 하지만 좌표가 게임 맵 (n x m) 을 벗어나면 안되니 해당하는 경우도 넘어간다
• 게임 맵 안에 있고, 벽이 아닌경우 해당 좌표들을 현재 좌표값 +1로 업데이트 해준다
• map[][] 의 끝이 탈출구이기 때문에 BFS를 수행하고 나면 해당 자리에는 총 이동횟수가 저장 되어있으니
• 해당 인덱스 값을 출력하면 된다. 만약 해당 값이 1이라면, 탈출구 까지 갈 수 없었던 것이기 때문에 -1을 return 한다

코드

import java.util.*;

class Solution {
    static class Node {
        int x, y, steps;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int[] dx = {0,0,-1,1};
    public static int[] dy = {1,-1,0,0};
    
    public int solution(int[][] maps) {

        
        int n = maps.length;
        int m = maps[0].length;
        bfs(0,0,maps,n,m);        
        if (maps[n-1][m-1] == 1) {
            return -1;
        }
        
        return maps[n-1][m-1];

    }
    
    public static void bfs(int x, int y, int[][] maps, int n, int m) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(x, y));
        
        while (!q.isEmpty()) {
            Node node = q.poll();
            for (int i=0; i<4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (ny >= m || nx >= n || nx < 0 || ny < 0) continue;
                if (maps[nx][ny] == 0) continue;
                if (maps[nx][ny] == 1) {
                    maps[nx][ny] = maps[node.x][node.y] + 1;
                    q.offer(new Node(nx, ny));
                }
            }
        }
        
    }
}