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

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

💡풀이 1

import java.util.ArrayDeque;
import java.util.Queue;

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

        int sizeX = maps.length; // x 길이
        int sizeY = maps[0].length; // y 길이

        //sizeX*sizeY 배열 visited 만들기
        boolean[][] visited = new boolean[sizeX][sizeY];

        //분기 - bfs
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});

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

            if(visited[x][y]) {
                continue;
            }
            visited[x][y] = true;

            // 상하좌우 커맨드를 추가하여 4번 분기
            int[] cx = new int[]{0, 0, 1, -1};
            int[] cy = new int[]{1, -1, 0, 0};

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

                //0보다 작아지는 경우
                if(nx < 0 || nx >= sizeX || ny < 0 || ny >= sizeY) {
                    continue;
                }

                //벽과 만나는 경우
                if(maps[nx][ny] == 0) {
                    continue;
                }

                //이미 방문한경우
                if(visited[nx][ny]) {
                    continue;
                }

                //해당위치에 현재위치 값 + 1 저장
                maps[nx][ny] = maps[x][y] + 1;

                //[sizeX-1][sizeY-1] 이면 return
                if(ny == sizeY - 1 && nx == sizeX - 1) {
                    return maps[nx][ny];
                }

                //queue에 저장
                queue.offer(new int[]{nx, ny});
            }
        }
        return -1;
    }
}

💡풀이 2

- 도달 거리를 maps가 아닌 int 배열에 저장하여 queue에 삽입

import java.util.ArrayDeque;
import java.util.Queue;

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

        // 상하좌우 커맨드
        final int[] cx = new int[]{0, 0, 1, -1};
        final int[] cy = new int[]{1, -1, 0, 0};

        int n = maps.length;
        int m = maps[0].length;
        boolean[][] visited = new boolean[n][m];

        //분기 - bfs
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0, 1});
        visited[0][0] = true;

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

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

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

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 0보다 작아지는 경우
                if(maps[nx][ny] == 0) continue; // 벽과 만나는 경우
                if(visited[nx][ny]) continue; // 이미 방문한경우
                visited[nx][ny] = true;

                queue.offer(new int[]{nx, ny, cnt + 1});
            }
        }

        return -1; // 도달하지 못하는 경우
    }
}

---

📖새로 배운 부분

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

---

GitHub - okjunghyeon/Programmers_CodingTest: 프로그래머스 관련 코딩테스트 문제를 풀이한 저장소입니다.