728x90
반응형
문제
N*M의 배열에서 (0,0) 에서 (N-1,M-1)까지 가는 최단거리를 구하여라
입력예제
첫째줄 N 과 M을 입력받으며, 두번째줄 부터 M개의 숫자들이 N줄 나옴
5 4
10 5 9 5
4 1 1 7
7 5 1 6
3 4 8 6
3 4 3 6
===> 답: 34
풀이 코드
다익스트라를 이용한 풀이 코드입니다. 위 예제를 이력하여 마지막에 나온 dist 배열의 값은
[10, 15, 24, 28]
[14, 15, 16, 23]
[21, 20, 17, 23]
[24, 24, 25, 29]
[27, 28, 28, 34]
입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n, m;
static int[][] MAP;
// Node 생성
static class Node implements Comparable <Node> {
int y;
int x;
int cost;
Node(int y, int x, int cost) {
this.y= y;
this.x=x;
this.cost=cost;
}
@Override
public int compareTo(Node next) {
if(cost < next.cost)
return -1;
if(cost > next.cost)
return 1;
return 0;
}
}
static int[] ydir = {0, 0, 1, -1};
static int[] xdir = {1, -1, 0, 0};
static void dijkstra(int y, int x) {
// 1. PQ 설정
PriorityQueue<Node>pq = new PriorityQueue<>();
// MAP[0][0] = 0, 0 위치로 진입하는 비용
pq.add(new Node(y, x, MAP[y][x]));
// 2. dist 설정
// dist[] = index : 노드번호 value : 최단거리
// dist[][] = [y][x] 좌표의 최단거리
int[][] dist = new int[n][m];
// 초기화
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
dist[i][j] = Integer.MAX_VALUE;
}
}
dist[y][x] = MAP[y][x];
// dijkstra
while(!pq.isEmpty()) {
Node now = pq.poll();
// 갈 수 있는 인접한 방향 체크
for(int i = 0; i < 4; i++) {
int ny = now.y + ydir[i];
int nx = now.x + xdir[i];
// ** 필수체크 ** 범위체크
if(ny < 0 || nx < 0 || ny >= n || nx >= m)
continue;
// 다음 노드까지의 비용
// 지금 좌표까지 오기 위해 사용한 비용 + 다음 좌표로 진입하기 위한 비용
int ncost = dist[now.y][now.x] + MAP[ny][nx];
// 지금까지 기록된 [ny][nx]까지의 최소비용보다 같거나 크면 pass
if(dist[ny][nx] <= ncost)
continue;
dist[ny][nx] = ncost;
pq.add(new Node(ny, nx, ncost));
}
}
System.out.println(dist[n-1][m-1]); // N-1,M-1 의 최단거리 출력
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
// map init
MAP = new int[n][m];
// input
for(int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < m; j++) {
MAP[i][j] = Integer.parseInt(st.nextToken());
}
}
dijkstra(0, 0); //(0,0) 부터 시작
}
}
다익스트라의 원리는 지난번 설명한 포스트에 있으니 참고하세요.
2021.06.14 - [Programe Note/Algorithm] - [Java] 다익스트라 알고리즘 - 최단경로
728x90
반응형
