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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844

이 문제는 게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 구하고, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 하는 문제이다.

즉, 캐릭터의 현재 위치에서부터 상대 진영까지의 최단경로를 구하는 문제이다.

여기까지만 보면 다익스트라나 프림 알고리즘으로 풀면 될 것 같지만, 캐릭터는 2차원 배열을 이동하며 상대 진영에 도달해야한다.

이 점 때문에, 단순하게 BFS로 해결이 가능해보인다.
너비 우선 탐색을 하게 되면, 시작점으로부터 동일한 거리만큼 떨어진 위치들을 차례로 확인하게 된다.
따라서 재방문하지 않는다면, 항상 캐릭터는 특정 위치로 이동시 최단경로를 이용하게 된다.

자, 이제 시간 복잡도를 따져보자. 2차원 배열에서의 BFS의 시간복잡도는 $O(NM)$이고, $1 \lt N, M \lt 100$이므로 대략 최대 $10^4$번의 연산이 이루어질 것이라 예측할 수 있따. 따라서, 시간내 통과가 가능하다.

2차원 배열이므로 dx,dy 테크닉과 BFS를 이용하여 문제를 해결해보자.

이를 코드로 구현하면 다음과 같다.

import java.util.*;

class Solution {
    static final int NOT_VISITED = 0, WALL = 0;
    static final int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

    public int solution(int[][] maps) {
        int n = maps.length - 1, m = maps[0].length - 1;
        int[][] visited = new int[n + 1][m + 1];

        Queue<Position> q = new LinkedList<>();
        q.add(new Position(0, 0));
        visited[0][0] = 1;
        while (!q.isEmpty()) {
            Position current = q.poll();
            int x = current.x, y = current.y;

            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (isInvalid(n, m, nx, ny) || visited[nx][ny] != NOT_VISITED || maps[nx][ny] == WALL) {
                    continue;
                }
                visited[nx][ny] = visited[x][y] + 1;
                q.add(new Position(nx, ny));
            }
        }

        return visited[n][m] != 0 ? visited[n][m] : -1;
    }

    private boolean isInvalid(int n, int m, int nx, int ny) {
        return nx < 0 || nx > n || ny < 0 || ny > m;
    }

    static class Position {
        int x;
        int y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

추가로, NOT_VISITED를 -1로 설정하는 것이 좋을지 고민해볼 필요가 있다.

문제에서 답이 없으면 -1을 리턴하라는 조건 때문에, NOT_VISITED를 -1로 설정하고 이로 visited배열의 모든 원소들을 NOT_VISITED로 설정한다면, 그대로 상대 진영 위치를 리턴하면 문제가 해결된다.
도착하지 못한 경우에는 -1을 리턴하게 되고, 도착한 경우에는 방문한 칸의 위치를 리턴하게 되기 때문이다.

하지만, 초기화 과정으로 인한 오버헤드 때문에 필자는 NOT_VISITED를 0으로 설정하고 visited배열을 그대로 사용하였다.