[JAVA] 알고리즘 문제풀이 - Greedy 기출문제 (다익스트라 알고리즘)

Greedy 기출문제 풀이

다익스트라 알고리즘

설명 : 아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로 그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)
입력 : 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보와 거리비용이 주어진다.
출력 : 1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요
풀이

package org.example;

import java.util.*;

class Point implements Comparable<Point> {
    int point;
    int value;

    public Point(int point, int value) {
        this.point = point;
        this.value = value;
    }

    @Override
    public int compareTo(Point p) {
        return this.point-p.point;
    }
}

public class Main {

    static List<List<Point>> list = new ArrayList<>();

    static int[] dis;

    public void solution(int idx) {
        PriorityQueue<Point> pQ = new PriorityQueue<>();
        pQ.offer(new Point(idx, 0));
        dis[idx]=0;
        while(!pQ.isEmpty()){
            Point tmp = pQ.poll();
            int tmp_p = tmp.point;
            int tmp_v = tmp.value;
            if(dis[tmp_p]<tmp_v) continue;
            for (Point edge : list.get(tmp_p)) {
                if(dis[edge.point]>edge.value+tmp_v){
                    dis[edge.point] = edge.value+tmp_v;
                    pQ.offer(new Point(edge.point, edge.value+tmp_v));
                }
            }
        }
    }

    public static void main(String[] args) {
        
        Main main = new Main();
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        dis = new int[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        for(int i=0; i<=n; i++){
            list.add(new ArrayList<Point>());
        }
        int m = scan.nextInt();
        for(int i=0; i<m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            list.get(a).add(new Point(b, c));
        }
        main.solution(1);

        for(int i=2; i<=n; i++){
            if(dis[i]==Integer.MAX_VALUE) System.out.println(i+" : possible");
            else System.out.println(i+" : "+dis[i]);
        }

    }
}

정리
- 우선 입력값을 각 이동 정점과 값을 담은 Point객체로 만들어 주고, 이를 기존 정점의 리스트로 담은 2중 리스트를 만들 것임
- 그리고 각 정점마다 이동 값을 담을 dis배열을 static으로 만들어 줌
- 기준이 되는 1을 매개변수로 하여 메서드에 진입
- 우선순위 큐에 현재 정점과 데이터 (1에서 1로 이동하는 값은 당연히 0)를 넣고, dis에도 0값을 담아줌
- 우선순위큐가 비지 않았을경우(=이동할 정점이 있을 경우)
- 그중 제일 적은 값을 꺼낸 다음(=우선순위 큐기때문에 poll만 해주면 됨) 현재 정점과 이동값을 변수에 담아주고
- 거기서 이동해야 하는 정점들을 반복을 돌림
- 현재값+이동정점값을 더한것이 기존의 dis[이동정점]의 값보다 작을 경우에만 교체, 새로운 정점의 이동경로를 재탐색함
- 이 과정이 모두 끝났음에도 dis값이 변동없이 계속 int 최대값이라면 이동되지 않는 변수로 감안하고 impossible을 출력함

IM

Greedy 기출문제 풀이

다익스트라 알고리즘