[JAVA] 백준 11779 - 최소비용 구하기2

https://www.acmicpc.net/problem/11779

다익스트라로 출발점에서 목적지까지의 최단 경로의 가중치를 구하되, 거쳐온 도시의 개수와 경로를 출력하는 문제이다.

이렇게만 봤을 때 사실 만만하게 생각했는데 예상치 못한 부분에서 시간을 많이 소비했다.

정점 리스트에 미리 N개의 정점을 만들어놓고 우선순위 큐에서 그 정점을 계속 뽑아서 썼는데 이게 같은 주소를 가진 객체가 중복으로 삽입되어서 가중치가 더 작은 쪽으로 변경되어 같은 정점을 두 번 반복해서 방문하는 형태가 나타났던 것이다.

그래서 new로 객체를 새로 만들어서 값을 세팅해 준 뒤 Insert하고 poll 할때 미리 만들어놓은 정점에 값을 입혀주는 방식을 사용했는데 메모리초과가 났다.

알고보니 visited 체크를 제대로 안하고 있어서 중복 정점 방문 가능성이 있었고 poll한 뒤 방문체크를 추가해주니 통과했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeCount = par(br.readLine());
        int vertexCount = par(br.readLine());
        List<Node111> nodeList = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            nodeList.add(new Node111(i));
        }
        for (int i = 0; i < vertexCount; i++) {
            int[] vertex = getArray(br.readLine());
            HashMap<Integer,Integer> map = nodeList.get(vertex[0]).bus;
            if(map.getOrDefault(vertex[1],100001)>vertex[2]){
                map.put(vertex[1],vertex[2]);
            }
        }
        int[] targets = getArray(br.readLine());
        int start = targets[0];
        int end = targets[1];
        boolean[] visited = new boolean[nodeCount+1];
        nodeList.get(start).weight=0;
        PriorityQueue<Node111> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight));
        pq.offer(nodeList.get(start));
        while(!pq.isEmpty()){
            Node111 node111 = pq.poll();
            if (visited[node111.value]) continue;
            int value = node111.value;
            nodeList.get(value).weight = Math.min(nodeList.get(value).weight, node111.weight);
            visited[node111.value] = true;
            if(node111.parent!=0&&node111.weight<=nodeList.get(node111.value).weight){
                nodeList.get(node111.value).path.addAll(nodeList.get(node111.parent).path);
            }
            if(node111.value==end){
                nodeList.get(end).weight = Math.min(nodeList.get(end).weight,node111.weight);
                break;
            }
            for (Integer i : node111.bus.keySet()) {
                if(node111.weight+node111.bus.get(i)<nodeList.get(i).weight && !visited[i]){
                    Node111 target = new Node111(i);
                    target.parent = node111.value;
                    target.weight = node111.weight+node111.bus.get(i);
                    target.bus = nodeList.get(i).bus;
                    pq.offer(target);
                }
            }
        }
        Node111 target = nodeList.get(end);
        System.out.println(target.weight);
        System.out.println(target.path.size());
        for (int i = target.path.size()-1; i >=0 ; i--) {
            System.out.print(target.path.get(i));
            if(i!=0)System.out.print(" ");
        }
    }


    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Node111{
    int value;
    int weight = Integer.MAX_VALUE/3;
    int parent = 0;
    HashMap<Integer, Integer> bus = new HashMap<>();
    List<Integer> path = new ArrayList<>();
    Node111(int v){
        this.value = v;
        this.path.add(this.value);
    }
}