본문으로 건너뛰기

3342 - Find Minimum Time to Reach Last Room II

info

풀이 키워드​

스포주의

다익스트라


풀이 코드​

info
  • 메모리: 108300 KB
  • 시간: 458 ms
class Solution {
    int n, m;
    int[][] minTime;
    int[] dy = {-1, 0, 0, 1};
    int[] dx = {0, -1, 1, 0};

    public int minTimeToReach(int[][] moveTime) {
        this.n = moveTime.length;
        this.m = moveTime[0].length;
        minTime = new int[n][m];
        for (int[] line : minTime) Arrays.fill(line, Integer.MAX_VALUE);
        minTime[0][0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e[2]));
        pq.add(new int[]{0, 0, 0});
        while (!pq.isEmpty()) {
            int[] e = pq.poll();
            int y = e[0];
            int x = e[1];
            int t = e[2];
            for (int d = 0; d < 4; ++d) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (ny < 0 || n <= ny || nx < 0 || m <= nx) continue;
                int nt = Math.max(t + (2-(ny+nx&1)), moveTime[ny][nx] + (2-(ny+nx&1)));
                if (minTime[ny][nx] <= nt) continue;
                minTime[ny][nx] = nt;
                pq.add(new int[]{ny, nx, nt});
            }
        }

        return minTime[n-1][m-1];
    }
}

풀이 해설​

Find Minimum Time to Reach Last Room I 에서 이동 가중치 조건만 바뀐 문제이다.

이전 문제에선 이동시 +1초를 해야 하지만, 이 문제에선 +1초 -> +2초 -> +1초 ... 를 반복한다.


📌 이동시간 일반화하여 구하기​

예를 들어 2 * 2 맵이라고 했을 때

(0, 0)에서 한 칸 이동하면 (1, 0) 또는 (0, 1)이고,

여기서 한 번 더 움직이면 (1, 1) 위치가 됨을 알 수 있다.

👉 즉, y좌표 + x좌표가 홀수이면 +1초, 짝수이면 +2초가 되는 것이다.

따라서 2-(ny+nx&1)초만큼이라고 정리해볼 수 있겠다.