[이것이 코딩 테스트다] 화성 탐사
업데이트:
문제
문제의 저작권은 ‘이것이 코딩테스트다’ 교재에 있습니다.
당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다.
화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용 (에너지 소모량)이 존재한다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하라. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.
입력 조건
- 첫째 줄에 학생들의 수 N(2 <= N <= 500)과 두 학생의 성적을 비교한 횟수 M(2 <= M <= 10,000)이 주어집니다.
- 다음 M개의 각 줄에는 두 학생의 성적을 비교한 결과를 나타내는 두 양의 정수 A, B가 주어집니다. 이는 A번 학생의 성적이 B번 학생보다 낮다는 것을 의미합니다.
출력 조건
- 첫째 줄에 성적 순위를 정확히 알 수 있는 학생이 몇 명인지 출력합니다.
입력 예시
3
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
출력 예시
20
19
36
접근방식
출발 노드에서 도착 노드까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용해 해결하였다.
1) map에 정점간의 비용 정보를 입력받고, dist에는 나중에 최소값을 저장해주기 위해 가장 최대값으로 초기화해준다.
2) 다익스트라로 그래프를 탐색하면서 (0, 0) → (N-1, N-1)로 가는 최소비용을 구한다.
- Node정보를 저장할 클래스를 만들어서 좌표값, 최단거리를 저장한다. 그리고
pq에서 최단거리의 노드를 pop하기 위해 Comparable을 구성한다. - 시작점 (0, 0)의 정보를 우선순위큐
pq에 먼저 넣는다. - 큐가 빌때까지 다음을 수행한다.
- 큐에서 노드를 하나 꺼내면 상하좌우를 탐색한다.
- 다음 노드가 그래프 범위내에서 이동가능한지 체크한다.
- 이동가능하다면 현재 노드의 최단거리인
dist[nx][ny]와 다음노드를 거쳐서 가는now.dist + map[nx][ny]를 비교해서 더 작은값을 최단거리로 갱신해준다. 그리고 다음 케이스에서 최단경로를 구하기 위해 큐에 넣어준다.
3) 그래프 탐색이 종료되면 dist[N-1][N-1]에는 (0, 0) → (N-1, N-1)로 가는 최단 거리가 저장되어있다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, T; // 정점 수, 테케 개수
static final int INF = 1000000000;
static int[][] map; // 전체 맵
static int[][] dist; // 최단거리 테이블
static PriorityQueue<Node> pq;
static int[][] dArr = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
static StringBuilder sb;
static class Node implements Comparable<Node> {
int x, y, dist;
public Node(int x, int y, int dist) {
this.x = x;
this.y = y;
this.dist = dist;
}
@Override
public int compareTo(Node o) { // 가중치 최소값 pop
return this.dist - o.dist;
}
}
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
sb = new StringBuilder();
for(int t=0; t<T; t++) {
N = Integer.parseInt(br.readLine());
map = new int[N][N];
dist = 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()); // 최소비용 저장
dist[i][j] = INF; // 초기에 가장 큰값으로 세팅
}
}
dijkstra(); // 그래프 탐색
sb.append(dist[N-1][N-1]+"\n");
}
System.out.println(sb.toString());
}
private static void dijkstra() {
pq = new PriorityQueue<Node>(); // 최소 가중치 먼저 나옴
// 초기 세팅
dist[0][0] = map[0][0]; // 시작점 (0,0)
pq.add(new Node(0, 0, dist[0][0]));
while (!pq.isEmpty()) {
Node now = pq.poll();
for (int d = 0; d < 4; d++) {
int nx = now.x + dArr[d][0];
int ny = now.y + dArr[d][1];
// 이동가능한지 체크
if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
// 현재 노드의 최단거리 > 다음 노드를 거쳐서 가는 거리가 더 작은 경우
if(dist[nx][ny] > now.dist + map[nx][ny]) {
dist[nx][ny] = now.dist + map[nx][ny]; //최단거리 갱신
pq.add(new Node(nx, ny, dist[nx][ny]));
}
}
}
}
}
}