백준_4485_젤다지[Java]

[문제링크]

N x N 격자에서 좌상단→우하단 최소 비용을 구하는 문제. 가중치가 모두 양수라 그냥 다익스트라면 된다. 그래도 우선순위큐로 바꿔야 마음이 편함.

구현 메모

• dict[y][x]는 시작점에서 (y,x)까지의 최소 비용.
• 4방향 이동 시 if (dict[ny][nx] > dict[cy][cx] + cost)로 완화.
• 큐가 ArrayDeque로 작성돼 있지만, 비용이 단조 증가한다는 보장이 없으므로 우선순위 큐로 교체하면 더 안전하다(현재 데이터셋에서도 통과).

코드 발췌

int[][] dist = new int[N][N];
for (int[] row : dist) Arrays.fill(row, INF);
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[2]-b[2]);
dist[0][0] = 0; pq.offer(new int[]{0,0,0});

while (!pq.isEmpty()) {
    int[] cur = pq.poll();
    int y = cur[0], x = cur[1], w = cur[2];
    if (w > dist[y][x]) continue;
    for (int d=0; d<4; d++) {
        int ny = y + dy[d], nx = x + dx[d];
        if (ny<0 || nx<0 || ny>=N || nx>=N) continue;
        int nw = w + matrix[y][x];
        if (nw < dist[ny][nx]) {
            dist[ny][nx] = nw;
            pq.offer(new int[]{ny, nx, nw});
        }
    }
}

결과

• 최종 비용은 dist[N-1][N-1] + matrix[N-1][N-1] (도착 칸 비용 더해주기).
• 공간 O(N^2), 시간 O(N^2 log N).