[프로그래머스] 게임 맵 최단거리 (JAVA)

프로그래머스 - [Level 2] 게임 맵 최단거리

프로그래머스

---

문제 분석

 

 

• 게임 맵(NXM)이 주어졌을 때, 내가 상대팀 진영(n-1,m-1)에 도달할 때 가장 적게 지나가는 칸의 개수을 출력해라.
  (도착할 수 없을 때는 -1을 출력)
• map에 0은 갈 수 없는 길이다.

---

 

해결 키 포인트

• BFS 이용
• 시간이 생각보다 여유롭지 않음 (시간초과 고려)
  • count를 지역변수로 두고 큐에 있는 걸 다 빼고 인접 노드를 다 넣는 방법 → 문제 X
  • 이웃셀 탐색하는 방법 → 문제 O, 제대로 구현해야함
  • + 추가적으로 queue에 넣기 전에, visited를 확인 상태로 변경하게 코드 수정해야함 (그렇지 않으면, 시간초과)

 

---

코드

 

import java.awt.*;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    int width, height;
    boolean isFinished = false;
    boolean[][] visited;
    int[][] maps;

    public int solution(int[][] maps) {
        this.maps = maps;
        width = maps.length;
        height = maps[0].length;
        visited = new boolean[width][height];
        int result = BFS(maps);
        if (isFinished) return result;
        else return -1;
    }

    public int BFS(int[][] maps) {
        // 최단 거리 개수
        int sum = 0;

        // 상하좌우 이동 배열
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 큐
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0, 0));

        while (!queue.isEmpty() && !isFinished) {
            int queueSize = queue.size();

            for (int j = 0; j < queueSize; j++) {
                Point point = queue.poll();
                int x = point.x;
                int y = point.y;

                if (check(x, y)) break;

                // 이웃 셀 탐색
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];

                    // 유효한 범위 내에 있고, 방문하지 않았으며, 벽이 아닌 경우
                    if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
                        if (!visited[nx][ny] && maps[nx][ny] == 1) {
                            // queue에 넣기 전에 visited 확인으로 변경
                            visited[nx][ny] = true;
                            queue.add(new Point(nx, ny));
                        }
                    }
                }
            }
            sum++;
        }
        return sum;
    }

    public boolean check(int x, int y) {
        if (x == width - 1 && y == height - 1) {
            isFinished = true;
            return true;
        } else return false;
    }
}