[JAVA][Programmers] 게임 맵 최단거리

프로그래머스

 

---

📌 접근 방법

이 문제는 BFS(너비 우선 탐색)를 사용하여 해결할 수 있습니다. BFS는 한 번에 여러 방향으로 탐색을 진행하기 때문에 최단 경로를 구하는 데 적합한 알고리즘입니다.

주어진 게임 맵에서 출발지점인 (0, 0)부터 도착지점인 (n-1, m-1)까지의 최단 경로를 구하는 문제이므로, BFS를 활용해 각 칸을 차례대로 탐색하면서 가장 빠르게 목표에 도달할 수 있는 경로를 찾는 방식입니다.

BFS는 큐(Queue)를 사용해 탐색을 진행합니다. 초기 상태에서 큐에 시작 지점 (0, 0)을 넣고, 각 칸을 방문하면서 이동 횟수를 함께 기록합니다. 큐에서 꺼낸 지점에서 상, 하, 좌, 우 4방향으로 이동하며, 벽이 아닌 곳만을 탐색하고, 이미 방문한 칸은 다시 방문하지 않도록 합니다. 목표 지점에 도달하면 해당 지점까지의 이동 횟수를 반환하며, 도달할 수 없다면 -1을 반환합니다.

[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)

 

---

PASS CODE

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int rows = maps.length;
        int cols = maps[0].length;

        int[] di = {-1, 1, 0, 0};
        int[] dj = {0, 0, -1, 1};

        boolean[][] visited = new boolean[rows][cols];

        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[] {0, 0, 1});
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            int [] current = queue.poll();
            int i = current[0];
            int j = current[1];
            int dist = current[2];

            if(i==rows - 1 && j==cols-1) {
                return dist;
            }
            for(int d=0; d<4; d++) {
                int ni = i + di[d];
                int nj = j + dj[d];

                if(ni >= 0 && ni < rows && nj >= 0 && nj < cols) {
                    if(maps[ni][nj] == 1 && !visited[ni][nj]) {
                        visited[ni][nj] = true;
                        queue.add(new int[] {ni, nj, dist+1});
                    }
                }
            }
        }
        return -1;
    }
}