이번에 풀어본 문제는
프로그래머스 게임 맵 최단거리 입니다.

📕 문제 링크

❗️코드

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

class ROR {
    int x, y;
    int moveCount;

    public ROR(int x, int y, int moveCount) {
        this.x = x;
        this.y = y;
        this.moveCount = moveCount;
    }
}
class Solution {
    static int N, M;
    static int answer = Integer.MAX_VALUE;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] isVisited;
    static Queue<ROR> q = new LinkedList<>();
    
    public int solution(int[][] maps) {
        N = maps.length;
        M = maps[0].length;
        isVisited = new int[N][M];

        q.add(new ROR(0, 0, 1));
        isVisited[0][0] = 1;

        while (!q.isEmpty()) {
            ROR cur = q.poll();

            if (cur.x == N - 1 && cur.y == M - 1) {
                answer = Math.min(answer, cur.moveCount);
                continue;
            }

            for (int idx = 0; idx < 4; idx++) {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if (isValid(mx, my) && maps[mx][my] > 0 && isBestWay(mx, my, cur.moveCount)) {
                    isVisited[mx][my] = cur.moveCount;
                    q.add(new ROR(mx, my, cur.moveCount + 1));
                }
            }
        }

        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < M;
    }

    static boolean isBestWay(int x, int y, int currentCount) {
        return isVisited[x][y] < 1 || isVisited[x][y] > currentCount;
    }
}

📝 풀이

간단한 그래프 탐색이라 생각해서 편한대로 dfs를 사용했더니 효율성이 걸리더군요..ㅋㅋㅋㅋ
그래서 bfs로 다시 풀었습니다.
bfs 탐색 시 방문 배열을 boolean으로 활용하게 되면, 더 나은 경우의 수가 해당 인덱스에 뒤늦게 방문하게 됐을 때 이미 방문한 것으로 판단하게 됩니다.
따라서 방문 배열을 int로 선언하고, 해당 인덱스에 방문한 시점에서의 이동 거리를 담아주면, 첫 방문 또는 이전 보다 더 짧은 이동 거리까지 고려해서 탐색을 진행할 수 있습니다.
마지막으로 answer이 초기화 했던 Integer.MAX_VALUE일 경우에는 끝까지 도달하지 못한 케이스기 때문에 반환 시 이부분만 체크해주면 됩니다.