[JAVA] bfs : 게임 맵 최단거리

1. 문제 내용

map의 시작점에서 끝점까지 좌표의 값이 1인 곳만 통해서 최단거리를 구하라
단, 경로가 없다면 -1을 반환

2. 접근 방법
최단경로를 구하는 문제이므로 BFS를 적용해 보았다

3. 구현 과정

int rows = maps.length;
int cols = maps[0].length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] visited = new boolean[rows][cols];
int[][] distance = new int[rows][cols];
int[] dy = {-1, 1, 0, 0};
int[] dx = {0, 0, -1, 1};

사용할 변수들

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

시작점 저장

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

    if (y == rows - 1 && x == cols - 1) {
        return dist;
    }

    for (int i = 0; i < 4; i++) {
        int nextY = y + dy[i];
        int nextX = x + dx[i];

        if (nextY >= 0 && nextY < rows && nextX >= 0 && nextX < cols
                && maps[nextY][nextX] == 1 && !visited[nextY][nextX]) {
            visited[nextY][nextX] = true;
            distance[nextY][nextX] = dist + 1;
            queue.offer(new int[]{nextY, nextX, dist + 1});
        }
    }
}

큐에서 값을 꺼낸 후 연산 시작
dx와 dy를 이용해 주변 칸을 모두 확인해서 이동 가능한 경로인지 체크 후 이동이 가능하다면 시작점부터 현재까지의 거리와 함께 큐에 삽입하고
끝점에 도착하면 거리값 반환

4. 결과

전체코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int solution(int[][] maps) {
        int rows = maps.length;
        int cols = maps[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[rows][cols];
        int[][] distance = new int[rows][cols];
        int[] dy = {-1, 1, 0, 0};
        int[] dx = {0, 0, -1, 1};

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



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

            if (y == rows - 1 && x == cols - 1) {
                return dist;
            }

            for (int i = 0; i < 4; i++) {
                int nextY = y + dy[i];
                int nextX = x + dx[i];

                if (nextY >= 0 && nextY < rows && nextX >= 0 && nextX < cols
                        && maps[nextY][nextX] == 1 && !visited[nextY][nextX]) {
                    visited[nextY][nextX] = true;
                    distance[nextY][nextX] = dist + 1;
                    queue.offer(new int[]{nextY, nextX, dist + 1});
                }
            }
        }

        return -1;
    }
}