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

문제

게임 맵 최단거리

📌 아이디어

이 문제는 그래프 탐색 문제로 최소 이동 경로를 찾아야 하는 문제입니다.

1. BFS를 활용해서 문제를 해결했습니다.
2. 시작 위치와 도착 위치가 고정이기 때문에 (0, 0)좌표를 큐에 삽입에 탐색을 시작합니다.
3. 기본적으로 상, 하, 좌, 우 4방향을 이동하도록하고 특정 조건에 만족한다면 이동 위치를 큐에 삽입하고 방문처리를 합니다.
4. 큐에서 나온 좌표가 만약 도착 위치라면 이동 횟수를 정답 처리합니다.
5. 하지만 정답 처리된 값이 0인 경우는 도착할 수 없는 경우이므로 -1로 정답 처리를 합니다.

📌 코드

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

class Solution {
    static int[] Di = {1, -1, 0, 0};
    static int[] Dj = {0, 0, 1, -1};

    static class Pos{ // 큐에 들어가기위한 인자들
        int i, j, cnt;
        public Pos(int i, int j, int cnt) {
            this.i = i;
            this.j = j;
            this.cnt = cnt;
        }
    }
    public int solution(int[][] maps) {
        int answer = 0;
        
        int N = maps.length; // 세로
        int M = maps[0].length; // 가로
        boolean[][] check = new boolean[N][M]; // 방문체크
        
        Queue<Pos> que = new LinkedList<>();
        que.add(new Pos(0, 0, 0)); // 세로, 가로, 이동횟수
        check[0][0] = true;
        
        while(!que.isEmpty()){
            Pos cur = que.poll();
            if (cur.i==N-1 && cur.j==M-1){
                answer = cur.cnt;
                break;
            }
            
            for(int d=0; d<Di.length; d++){
                int ni = cur.i + Di[d];
                int nj = cur.j + Dj[d];
                // 이동 가능한 경우 큐에 추가 및 방문 체크
                if (0 <= ni && ni < N && 0 <= nj && nj < M){
                    if (maps[ni][nj] == 1 && !check[ni][nj]){
                        check[ni][nj] = true;
                        que.add(new Pos(ni, nj, cur.cnt+1));
                    }
                }
            }
        }
        if (answer == 0){
            answer = -1;
        } else {
            answer += 1;
        }
        
        return answer;
    }
}

피드백 및 개선점은 댓글을 통해 알려주세요😊