[JAVA] 백준 1753 - 최단경로

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

정석적인 다익스트라를 이용하는 문제인데, input으로 주어지는 정점과 간선의 개수가 심상치 않았다.

특이한 점으론 두 정점 A,B를 잇는 간선이 여러개가 있을 수 있다는 것이다.

이러한 경우 다익스트라 알고리즘을 이용하는 부분 중 우선순위 큐에 간선을 삽입할 때, 목적지 정점의 가중치가 아직 초기화되지 않은 상태라면 동일한 간선(가중치만 다른)이 여러개 들어가 시간초과가 일어날 것 같아서 이를 해소하는 방법에 대해서 생각하게 되었다.

일반적으로 정점 클래스를 선언할 때, ArrayList에 간선을 담아서 보관했는데 이런 경우 중복제거가 힘드므로 정점 멤버 변수 안에  HashMap을 선언하고, 간선 데이터를 읽으면서 해당 map에 <목적지 정점번호, 가중치>를 삽입할 때 목적지 정점번호를 이미 Key로 가지고 있을 경우 새로운 간선의 가중치가 더 낮을 경우에만 value를 업데이트하도록 구현하고, 우선순위큐 사용을 편하게 하기 위해 모든 간선 데이터를 읽은 후 이를 ArrayList 형태로 변환하는 방법을 사용했다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int startNode = Integer.parseInt(br.readLine());
        int nodeCount = a[0];
        List<node> nodeList = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            nodeList.add(new node(i));
        }
        int vertexCount = a[1];
        for (int i = 0; i < vertexCount; i++) {
            a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if(!nodeList.get(a[0]).map.containsKey(a[1])){
                nodeList.get(a[0]).map.put(a[1],a[2]);
            }else{
                int value = nodeList.get(a[0]).map.get(a[1]);
                if(value>a[2]){
                    nodeList.get(a[0]).map.put(a[1],a[2]);
                }
            }
        }
        nodeList.forEach(node::convert);


        PriorityQueue<Vertex2> pq = new PriorityQueue<>();
        pq.addAll(nodeList.get(startNode).nodeList);
        nodeList.get(startNode).weight = 0;
        while (!pq.isEmpty()) {
            Vertex2 target = pq.poll();
            int from = target.from;
            int to = target.to;
            int cost = target.value;
            if (nodeList.get(to).weight < nodeList.get(from).weight + cost) continue;
            nodeList.get(to).weight = nodeList.get(from).weight + cost;
            for (int i = 0; i < nodeList.get(to).nodeList.size(); i++) {
                Vertex2 v = nodeList.get(to).nodeList.get(i);
                if(v.value+ nodeList.get(v.from).weight<nodeList.get(v.to).weight) pq.add(v);
            }
        }

        for (int i = 1; i <= nodeCount; i++) {
            if(nodeList.get(i).weight==Integer.MAX_VALUE){
                System.out.println("INF");
            }else System.out.println(nodeList.get(i).weight);
        }
    }
}
class node {
    int value;
    HashMap<Integer, Integer> map = new HashMap<>();
    List<Vertex2> nodeList = new ArrayList<>();
    int weight = Integer.MAX_VALUE;

    node(int value) {
        this.value = value;
    }

    void convert(){
        this.nodeList = this.map.keySet().stream().map(x-> new Vertex2(this.value, x, map.get(x))).collect(Collectors.toList());
    }
}
class Vertex2 implements Comparable<Vertex2> {
    int from;
    int to;
    int value;

    Vertex2(int from, int to, int value) {
        this.from = from;
        this.to = to;
        this.value = value;
    }

    @Override
    public int compareTo(Vertex2 o) {
        return this.value - o.value;
    }
}

 

List.foreach 구문에 실수로 for문을 걸어버리는 바람에 O(N^2)짜리 무의미한 코드를 넣어버려서 시간 초과가 났었다.