Lv.2 : 게임 맵 최단거리

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• n x m 맵에서 (0, 0) 부터 (n-1, m-1) 까지 이동하는데 최단거리를 반환한다.
• 만약 도달할 수 없다면 -1을 반환한다.

🔸 문제 풀이 🔸

• 전형적인 최단거리 문제로 너비 우선 탐색(BFS)로 풀이할 수 있다.

---

🔸 코드 🔸

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

class Solution {
    private static class Point {
        private int row, col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    public int solution(int[][] maps) {
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        int cnt = 1;
        int findR = maps.length - 1;
        int findC = maps[0].length - 1;

        Queue<Point> que = new ArrayDeque<>();
        boolean[][] visited = new boolean[maps.length][maps[0].length];

        que.add(new Point(0, 0));
        visited[0][0] = true;

        while (!que.isEmpty()) {
            int size = que.size();

            for (int i = 0; i < size; i++) {
                Point point = que.poll();

                if (point.row == findR && point.col == findC) {
                    return cnt;
                }

                for (int j = 0; j < dx.length; j++) {
                    int newR = point.row + dx[j];
                    int newC = point.col + dy[j];

                    if (0 <= newR && newR <= findR && 0 <= newC && newC <= findC && !visited[newR][newC] && maps[newR][newC] == 1) {
                        visited[newR][newC] = true;
                        que.add(new Point(newR, newC));
                    }
                }
            }

            cnt++;
        }

        return -1;
    }
}

🔸 코드 해석 🔸

• BFS를위해 좌표를 큐로 관리해야 하므로, Point 클래스를 만들어 사용했다.
• 최단거리를 구하는 BFS 과정에서 한 번이라도 방문한 좌표는 최단 거리를 구한 것이므로 방문체크를 통해 중복 검사를 방지한다.
• 현재 큐 사이즈만큼 반복해서 현재 움직인 횟수를 관리한다.

---

🔸 end 🔸

• BFS 문제를 오랜만에 풀어봤는데 간단히 풀이할 수 있었다.
• 채점에 효율성 테스트 부분이 있는데 방문체크를 하지 않으면 걸리는 것 같다.