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

사진을 클릭하면 해당 문제로 이동

💡풀이 1

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {

    public int solution(int[][] maps) {

        final int[] dx = {1, -1, 0, 0};
        final int[] dy = {0, 0, 1, -1};
        final int n = maps.length, m = maps[0].length;

        boolean[][] visited = new boolean[n][m];
        Deque<int[]> queue = new ArrayDeque<>();

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

        while(!queue.isEmpty()) {

            int[] now = queue.poll();
            int x = now[0], y = now[1], count = now[2];

            if(x == n - 1 && y == m - 1) {
                return count;
            }

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

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[nx][ny] == 0) continue;
                if(visited[nx][ny]) continue;

                visited[nx][ny] = true;
                queue.offer(new int[]{nx, ny, count + 1});

            }
        }

        return -1;
    }
}

---

📖새로 배운 부분

• BFS (너비 우선 탐색): 최단 경로나 최소 비용이 필요할 때 사용하며, 시작점에서 가까운 순서대로 탐색합니다.
• DFS (깊이 우선 탐색): 경로의 존재 여부 확인이나, 가능한 모든 경우의 수를 탐색해야 하는 백트래킹 문제에 적합합니다.
• 간단히 말해, '가장 빠른 길'은 BFS, '길이 있는지' 또는 '모든 길'은 DFS를 사용하면 좋습니다.

---

참고

• https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스