[JAVA] 다익스트라 이용 최단거리 문제 풀이(배열)

문제

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] 다익스트라 알고리즘 - 최단경로