문제
N x N 동굴의 각 칸에 도둑루피(잃는 금액)가 있을 때, (0,0)에서 (N-1,N-1)까지 잃는 금액의 최솟값을 구하라.
입력
여러 테스트 케이스가 주어지며, 각 케이스에 N과 N x N 격자가 주어진다. N=0이면 종료.
출력
각 케이스마다 최소 손실 금액을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 5 5 4 3 9 1 3 2 7 0 | Problem 1: 20 |
풀이
다익스트라 알고리즘을 격자 그래프에 적용하여 최소 비용 경로를 구한다.
- 시작점의 비용을 초기화하고 우선순위 큐에 넣는다
- 4방향 인접 칸으로 이동 비용을 갱신하며 탐색한다
dijk[nr][nc] > dijk[r][c] + map[nr][nc]이면 갱신한다- (N-1,N-1)의 최종 비용이 답이다
핵심 아이디어: 격자의 각 칸을 노드로, 이동 비용을 간선 가중치로 보면 다익스트라로 최소 비용 경로를 구할 수 있다.
코드
package day599;
import java.io.*;
import java.util.*;
public class Day559BOJ4485젤다 {
static class point implements Comparable<point> {
int row, col, cost;
public point(int row, int col, int cost) {
super();
this.row = row;
this.col = col;
this.cost = cost;
}
@Override
public int compareTo(point o) {
return this.cost - o.cost;
}
}
static int N;
static int[][] map;
static int[][] dijk;
static int[] dy = { 0, 1, -1, 0 };
static int[] dx = { 1, 0, 0, -1 };
// 범위 검사
static boolean isValid(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= N)
return false;
return true;
}
public static int dijkstra() {
PriorityQueue<point> pq = new PriorityQueue<point>();
dijk[0][0] = map[0][0];
pq.offer(new point(0, 0, map[0][0]));
while (!pq.isEmpty()) {
point p = pq.poll();
for (int k = 0; k < 4; k++) {
int nextRow = p.row + dy[k];
int nextCol = p.col + dx[k];
if (isValid(nextRow, nextCol)) {
if (dijk[nextRow][nextCol] > dijk[p.row][p.col] + map[nextRow][nextCol]) { // 기존의 가중치보다 작은 경우
dijk[nextRow][nextCol] = dijk[p.row][p.col] + map[nextRow][nextCol]; // 가중치를 교환
pq.offer(new point(nextRow, nextCol, dijk[nextRow][nextCol])); // 큐에 추가
}
}
}
}
return dijk[N - 1][N - 1];
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int cnt = 0;
while (true) {
N = Integer.parseInt(br.readLine());
if (N == 0)
break;
map = new int[N][N];
dijk = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
dijk[i][j] = Integer.MAX_VALUE;
}
}
cnt++;
sb.append("Problem " + cnt + ": " + dijkstra() + "\n"); // 출력문
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N² log N)
- 공간: O(N²)