[백준]최소비용 구하기2(11779번)

https://www.acmicpc.net/problem/11779
//1 문제 분석

그래프에서 간선에 가중치가 있는 경우 목적지까지 최소 비용을 구하는 문제이다. 특이점으로는 도착지까지의 경로가 항상 존재한다고 문제에 명시되어 있다.

//2 문제 해결

음의 가중치가 없으니 다익스트라 알고리즘을 적용하여 최소값을 찾았고 기본 방문 배열을 이차원 배열로 만들어 이전 경로에 대한 정보를 저장하였다.

//3 작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class MinimumCost2_11779 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz;
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        ArrayList<int[]>[] graph = new ArrayList[n+1];
        for (int i = 0 ; i<n+1 ; i++){
            graph[i]=new ArrayList<>();
        }
        for (int i = 0 ; i<m ; i++) {
            stz = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stz.nextToken());
            int b = Integer.parseInt(stz.nextToken());
            int c = Integer.parseInt(stz.nextToken());
            graph[a].add(new int[]{b,c});
        }
        stz = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(stz.nextToken());
        int end = Integer.parseInt(stz.nextToken());
        int[][] visited = new int[n+1][2];
        Dijk ans = dijkstra(graph,start,end,visited);
        StringBuilder sb = new StringBuilder();
        sb.append(ans.getCost()).append("\n");
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        int temp = end;
        int num = 0;
        while(temp!=0){
            num++;
            dq.addFirst(temp);
            temp=visited[temp][1];
        }
        sb.append(num).append("\n");
        while(!dq.isEmpty()){
            sb.append(dq.poll()).append(" ");
        }
        System.out.println(sb);

    }
    static Dijk dijkstra(ArrayList<int[]>[] graph , int start, int end, int[][] visited) {
        PriorityQueue<Dijk> q = new PriorityQueue<>();
        q.add(new Dijk(0,start));
        int[] dis = new int[graph.length];
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[start]=0;
        while(!q.isEmpty()){
            Dijk temp = q.poll();
            int loc = temp.getLoc();
            int cost = temp.getCost();
            if (loc==end) {
                return temp;
            }
            if (visited[loc][0]==1) continue;
            visited[loc][0]=1;
            for (int[] arr : graph[loc]){
                if(visited[arr[0]][0]==0){
                    if(dis[arr[0]]>cost+arr[1]){
                        dis[arr[0]]=cost+arr[1];
                        visited[arr[0]][1]=loc;
                        q.add(new Dijk(cost+arr[1],arr[0]));
                    }
                }
            }
        }
        return new Dijk(0,0);
    }
    static class Dijk implements Comparable<Dijk>{
        private int cost;
        private int loc;
        public Dijk(int cost, int loc) {
            super();
            this.cost = cost;
            this.loc = loc;
        }
        public int getCost() {
            return cost;
        }
        public int getLoc() {
            return loc;
        }
        @Override
        public int compareTo(Dijk o) {
            if (this.cost>o.getCost()) {
                return 1;
            } else if (this.cost==o.getCost()) {
                return 0;
            } else {
                return -1;
            }
        }
    }
}

//4 시행착오

처음에 코드를 작성할 때, 간선에 대한 정보를 2차원 배열안에 비용을 저장하는식으로 구현하였다. 이때 초기화시 값이 0으로 초기화되어서 값이 0인 경우 연결이 없는것으로 생각하였는데, 비용이 0인 입력도 주어질 수 있어서 그 경우 원하는 출력을 얻지 못했다. 이는 정보를 ArrayList로 저장하도록 바꾸는 과정에서 해결하였다.

//5 개선 가능성

다익스트라 메서드에서 이번 코드에서 정의한 dijk 객체를 반환하였다. 이는 처음 계획에서 dijk 객체 안에 경로나 몇개의 노드를 지났는지 등의 정보를 저장할 예정이여서 그렇게 하였으나, 마지막으로 작성한 코드에서는 그럴 필요가 없어졌다.
작성하는 과정에서 main메서드가 너무 길어져서 가독성이 너무 나빠졌는데 기능을 좀 더 분류하고 메서드로 묶어서 표현하면 더 괜찮을 것 같다.