Skip to main content

3341 - Find Minimum Time to Reach Last Room I

info

풀이 키워드​

스포주의

다익스트라


풀이 코드​

info
  • 메모리: 45000 KB
  • 시간: 11 ms
import java.util.*;

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);

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        pq.add(new int[]{0, 0, 0});
        minTime[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; // out of bound
                int nt = Math.max(t+1, moveTime[ny][nx]+1);
                if (minTime[ny][nx] <= nt) continue; // better one exists -> drop this
                minTime[ny][nx] = nt;
                pq.add(new int[]{ny, nx, nt});
            }
        }

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

풀이 해설​

각 칸별 입장 시간의 제약조건을 가중치로 치환하여 생각하면 되고,

가중치 그래프에서의 최단 경로는 다익스트라로 찾는다.


note

왜 BFS 안됨?​

릿코 댓글에 하도 bfs 안된다거리길래 아예 안먹히나 싶은데 생각해보니 그냥 덜 효율적일 뿐 가능은 할 것 같은데?

우선순위 큐로 작은 시간에 도달한 경우부터 처리하는 이유는, 그 경우가 다음 이동 지점에 타 경로보다 더 작은 시간으로 도달할 확률이 높기 때문이고

더 작은 시간 값을 minTime 배열에 먼저 기록해뒀을수록 drop 기준이 빡세지니 탐색 수가 줄어들기 때문이다.


note

왜 DP 안됨?​

DP같은 경우 메모이제이션이 필수적으로 들어간다. 캐싱 안하면 걍 완탐이므로.

그렇다면 메모이제이션의 의도를 생각해보자.

하향식으로 구현한다는 가정 하에, dp 함수의 반환값은 그 칸에 도달한 최소 시간으로 정의되고

따라서 메모이제이션 값도 그 칸에 도달한 최소 시간을 의미한다.


어떠한 dp 함수가 메모이제이션 값을 참조하려는 상황을 고려해보면

memo[y][x]를 참조할 것이고 이게 최소 시간임을 보장해야되는데, 보장이 안된다. 왜냐?

memo가 특정 state에 대한 일종의 visited 역할을 해서 재방문(=중복연산)을 막는 목적인데

이 문제는 타 경로로 도달한게 더 최적일 수도 있기 때문이다.

다시말해 memo에 쓰인 값보다, 이 memo를 참조하려는 현 호출된 함수의 처리 결과가 더 좋을 수도 있다.


따라서 memo[y][x]는 잘못된 state 정의의고,

memo의 최적성을 보장하려면 memo[y][x][t]로 시간별 메모이제이션을 해주어야 한다.

하지만 이러면 메모이제이션의 의미가 매우 떨어지게 된다.


그러면 memo값 그대로 리턴하지 말고, memo에 쓰인 값이랑 현재 함수의 도착 시간이랑 비교해서 리턴할지 재귀할지 판단하면 되지 않음?

이라고 생각할 수 있다.

그러면 DP가 아니게 되고 다익스트라가 해당 방식을 사용한다. 이해 끝! 😉


📌 우선순위 큐와 힙의 차이​

헷갈리면 안된다.

  • 우선순위 큐 -> 추상적인 자료형(data type)
  • 힙 -> 구체적인 자료구조(data structure)

자료형은 그냥 추상적으로 이러한 규칙으로 작동하는 무언가~ 같은거고 (=이론)

자료구조는 시간복잡도 다 고려해서 구현되는 구체적인 구현체이다.

따라서 힙은 우선순위 큐의 구현체이고, 우선순위 큐의 구현체가 힙이 아니게 될 수도 있다. (더 좋은게 발견되면!)

정렬도 각 언어별로 내부 구현 방식이 다르듯이 말이다.


메모​

  • 다익 구현 자체는 쉬워서 제출 1트컷 했다 👍
  • 풀이 시간 짧다고 복습 안하면 안된다.. 이 유형 문제 볼 일이 생각보다 없어서 실전에서 갑툭튀할 시 대참사 일어남
    • 잘 안써서 까먹기 좋은데 기습 출제해놓고 '그것도 몰라?' 하기 딱 좋은 유형.